我正在解決一個演算法問題，其提示是：
“給定一個字串 s，找出最長的子串的長度而不重復字符。”
我有兩個公認的解決方案，如下所示：
function lengthOfLongestSubstring(s: string): number {
let longestStr = '';
let maxLength = 0;
for (let i = 0; i < s.length; i = 1) {
//solution 1
if (longestStr.split('').includes(s[i])) {
longestStr = longestStr.slice(longestStr.split('').indexOf(s[i]) 1);
}
longestStr = s[i];
if (longestStr.length > maxLength) {maxLength = longestStr.length}
// solution 2
longestStr = s[i];
if(longestStr.indexOf(s[i]) !== longestStr.length - 1) {
longestStr = longestStr.slice(longestStr.indexOf(s[i]) 1)
}
if (longestStr.length > maxLength) {maxLength = longestStr.length}
}
return maxLength;
}
兩種解決方案的區別在于是在 if 陳述句之前還是之后引入這段代碼。
longestStr = s[i];
會導致時間/空間復雜性的代碼的唯一區別是各個 if 陳述句中的代碼。
解決方案 1 的性能要好得多：214ms，44.9MB
解決方案 2 明顯更差：607ms，47MB
解決方案1：根據string.Split方法的運行時間，.split方法的時間復雜度為O(n)。
.includes方法必須有 O(n) 因為它回圈一次。
解決方案2：根據javascript的array.indexOf的時間復雜度是多少？,.indexOf有 O(n)。
.length是一種可在所有可列舉的 Javascript 物件（陣列）中訪問的方法，在陣列中查找是 O(1)。
除非我上面的時間復雜度不正確，否則解決方案 2 似乎需要更少的時間。然而，情況完全相反。
請幫我理解，謝謝
uj5u.com熱心網友回復：
你說得對。解決方案 1 的性能應該更差。確實如此，至少根據我的測驗：
function lengthOfLongestSubstring(s) {
let longestStr = ''
let maxLength = 0
for (let i = 0; i < s.length; i = 1) {
//solution 1
if (longestStr.split('').includes(s[i])) {
longestStr = longestStr.slice(
longestStr.split('').indexOf(s[i]) 1
)
}
longestStr = s[i]
if (longestStr.length > maxLength) {
maxLength = longestStr.length
}
}
return maxLength
}
function lengthOfLongestSubstring2(s) {
let longestStr = ''
let maxLength = 0
for (let i = 0; i < s.length; i = 1) {
// solution 2
longestStr = s[i]
if (longestStr.indexOf(s[i]) !== longestStr.length - 1) {
longestStr = longestStr.slice(longestStr.indexOf(s[i]) 1)
}
if (longestStr.length > maxLength) {
maxLength = longestStr.length
}
}
return maxLength
}
let s1 = ''
const slen = 1000000
const letters = 'abcdeghijklmnop'
for (let i = 0; i < slen; i ) {
s1 = s1 letters[Math.random() * letters.length]
}
console.time('solution1')
console.log(lengthOfLongestSubstring(s1))
console.timeEnd('solution1')
console.time('solution2')
console.log(lengthOfLongestSubstring2(s1))
console.timeEnd('solution2')
// result: solution 1: 1.484s, solution 2: 317ms
你看到同樣的事情嗎？
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/420798.html
標籤：