[[421075]]

本文轉載自微信公眾號「三分鐘學前端」，作者sisterAn 。轉載本文請聯系三分鐘學前端公眾號。

給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。

示例 1:

輸入: "abcabcbb" 
輸出: 3  
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。 

示例 2:

輸入: "bbbbb" 
輸出: 1 
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。 

示例 3:

輸入: "pwwkew" 
輸出: 3 
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。 
     請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。 

解法一：維護數組

解題思路： 使用一個數組來維護滑動窗口

遍歷字符串，判斷字符是否在滑動窗口數組里

• 不在則 push 進數組
• 在則刪除滑動窗口數組里相同字符及相同字符前的字符，然后將當前字符 push 進數組
• 然后將 max 更新為當前最長子串的長度

遍歷完，返回 max 即可

畫圖幫助理解一下：

代碼實現：

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 
}; 

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

空間復雜度：O(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 
}; 

時間復雜度：O(n2)

空間復雜度：O(n)

解法三：優化的Map

解題思路：

使用 map 來存儲當前已經遍歷過的字符，key 為字符，value 為下標

使用 i 來標記無重復子串開始下標，j 為當前遍歷字符下標

遍歷字符串，判斷當前字符是否已經在 map 中存在，存在則更新無重復子串開始下標 i 為相同字符的下一位置，此時從 i 到 j 為最新的無重復子串，更新 max ，將當前字符與下標放入 map 中

最后，返回 max 即可

代碼實現：

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 
}; 

時間復雜度：O(n) 

空間復雜度：O(n)