[[421075]]

本文轉(zhuǎn)載自微信公眾號(hào)「三分鐘學(xué)前端」，作者sisterAn 。轉(zhuǎn)載本文請(qǐng)聯(lián)系三分鐘學(xué)前端公眾號(hào)。

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

示例 1:

輸入: "abcabcbb" 
輸出: 3  
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。 

示例 2:

輸入: "bbbbb" 
輸出: 1 
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。 

示例 3:

輸入: "pwwkew" 
輸出: 3 
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。 
     請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。 

解法一：維護(hù)數(shù)組

解題思路： 使用一個(gè)數(shù)組來(lái)維護(hù)滑動(dòng)窗口

遍歷字符串，判斷字符是否在滑動(dòng)窗口數(shù)組里

• 不在則 push 進(jìn)數(shù)組
• 在則刪除滑動(dòng)窗口數(shù)組里相同字符及相同字符前的字符，然后將當(dāng)前字符 push 進(jìn)數(shù)組
• 然后將 max 更新為當(dāng)前最長(zhǎng)子串的長(zhǎng)度

遍歷完，返回 max 即可

畫(huà)圖幫助理解一下：

代碼實(shí)現(xiàn)：

var lengthOfLongestSubstring = function(s) { 
    let arr = [], max = 0 
    for(let i = 0; i < s.length; i++) { 
        let index = arr.indexOf(s[i]) 
        if(index !== -1) { 
            arr.splice(0, index+1); 
        } 
        arr.push(s.charAt(i)) 
        max = Math.max(arr.length, max)  
    } 
    return max 
}; 

時(shí)間復(fù)雜度：O(n2)， 其中 arr.indexOf() 時(shí)間復(fù)雜度為 O(n) ，arr.splice(0, index+1) 的時(shí)間復(fù)雜度也為 O(n)

空間復(fù)雜度：O(n)

解法二：維護(hù)下標(biāo)

解題思路： 使用下標(biāo)來(lái)維護(hù)滑動(dòng)窗口

代碼實(shí)現(xiàn)：

var lengthOfLongestSubstring = function(s) { 
    let index = 0, max = 0 
    for(let i = 0, j = 0; j < s.length; j++) { 
        index = s.substring(i, j).indexOf(s[j])  
        if(index !== -1) {  
            i = i + index + 1  
        }  
        max = Math.max(max, j - i + 1)  
    } 
    return max 
}; 

時(shí)間復(fù)雜度：O(n2)

空間復(fù)雜度：O(n)

解法三：優(yōu)化的Map

解題思路：

使用 map 來(lái)存儲(chǔ)當(dāng)前已經(jīng)遍歷過(guò)的字符，key 為字符，value 為下標(biāo)

使用 i 來(lái)標(biāo)記無(wú)重復(fù)子串開(kāi)始下標(biāo)，j 為當(dāng)前遍歷字符下標(biāo)

遍歷字符串，判斷當(dāng)前字符是否已經(jīng)在 map 中存在，存在則更新無(wú)重復(fù)子串開(kāi)始下標(biāo) i 為相同字符的下一位置，此時(shí)從 i 到 j 為最新的無(wú)重復(fù)子串，更新 max ，將當(dāng)前字符與下標(biāo)放入 map 中

最后，返回 max 即可

代碼實(shí)現(xiàn)：

var lengthOfLongestSubstring = function(s) { 
    let map = new Map(), max = 0 
    for(let i = 0, j = 0; j < s.length; j++) { 
        if(map.has(s[j])) { 
            i = Math.max(map.get(s[j]) + 1, i) 
        } 
        max = Math.max(max, j - i + 1) 
        map.set(s[j], j) 
    } 
    return max 
}; 

時(shí)間復(fù)雜度：O(n) 

空間復(fù)雜度：O(n)