大廠高頻面試真題詳解：最長無重複字元的子串

給定一個字元串，請找出其中無重複字元的最長子字元串。

線上評測位址：

領扣題庫官網 樣例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 最長子串是 "abc".           

樣例 2:

輸入: "bbbbb"
輸出: 1
解釋: 最長子串是 "b".           

解題思路

• 暴力解法時間複雜度較高，會達到O(n^3)，故而采取滑動視窗的方法降低時間複雜度。
• 我們使用兩個指針表示字元串中的某個子串的左右邊界。每步操作中，右指針向右移動一位，然後不斷移動左指針，直到這兩個指針對應的子串中沒有重複的字元。在移動結束後，這個子串就對應着以右指針結束的，不包含重複字元的最長子串。我們記錄下這個子串的長度。
• 在枚舉結束後，我們找到的最長的子串的長度即為答案。

算法流程

• window是滑窗内字元的集合，初始化為空。從前向後移動滑窗，同時更新目前子串長度cur_len和最長子串長度max_len。當滑窗右端移動到字元ch：
  • 如果ch已存在window中，那麼從滑窗的左端起删除字元，直到删除ch。每删除一個字元cur_len減1。
  • 将ch添加到window中，cur_len加1。
  • 更新最長子串長度max_len。
• 傳回max_len。

複雜度分析

• 時間複雜度：O(n)，n為字元串s長度。左指針和右指針分别會周遊整個字元串一次。

• 空間複雜度：O(|Σ|)。Σ為字元串s中出現的字元集。由于我們使用哈希表來存儲子串的字元，是以空間複雜度為O(|Σ|)。

  代碼

class Solution {

public int lengthOfLongestSubstring(String s) {

        if (s == null) {
            return 0;
        }

        HashSet<Character> window = new HashSet<Character>();

        int left = 0, curLen = 0, maxLen = 0;
        char[] sc = s.toCharArray();

        for (char ch: sc) {

            // 從前向後删除，直到删除了ch
            while (window.contains(ch)) {

                window.remove(sc[left]);
                left ++;
                curLen --;
            }
            // 添加ch
            window.add(ch);
            curLen ++;
            // 更新長度
            maxLen = Math.max(maxLen, curLen);
        }
        return maxLen;
    }
}           

更多題解參考：

九章官網solution