LeetCode Longest Substring Without Repeating Characters：O(n) 滑動窗口 + 哈希表完美解法

題目要求

給定字符串，找出不含重複字符的最長子串長度。例如 "abcabcbb" 最長為 "abc" 長度 3；"bbbbb" 最長為 "b" 長度 1。

暴力法缺陷

枚舉所有子串並用哈希表檢查重複，最壞 O(n^2)，不可取。

O(n) 核心洞察

維護一個滑動窗口 [start, i] 表示當前無重複子串。遍歷字符 s[i]：

• 若 s[i] 未在窗口中出現 → 窗口右擴，長度 +1
• 若 s[i] 在窗口中上次出現位置為 last[s[i]] → 窗口左邊界跳至 last[s[i]] + 1（保證無重複且盡可能長）

關鍵：last[] 數組記錄每字符最後出現位置，初始化為 -1。窗口起始前一位置用 idx 記錄（初始 -1）。

優雅實現

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int last[256]; 
        fill(last, last+256, -1);
        int idx = -1, maxLen = 0;
        for (int i = 0; i < s.size(); i++) {
            if (last[s[i]] > idx) idx = last[s[i]]; // 縮窗
            if (i - idx > maxLen) maxLen = i - idx; // 更新答案
            last[s[i]] = i; // 記錄位置
        }
        return maxLen;
    }
};

圖解過程

以 "abbdeca" 為例：

• i=0 'a': idx=-1, maxLen=1, last['a']=0
• i=1 'b': idx=-1, maxLen=2, last['b']=1
• i=2 'b': last['b']=1 > idx → idx=1, maxLen=max(2,1)=2, last['b']=2
• i=3 'd': idx=1, maxLen=max(2,2)=2, last['d']=3
• ... 最終 maxLen=4 ("deca")

為什麼是 O(n)？

每字符僅被訪問一次，idx 單調遞增，無回溯。哈希表查詢 O(1)。總操作 ~2n。

對比註釋版暴力法

代碼中註釋部分為 O(n^2) 暴力法，利用「若剩餘長度 ≤ 當前最大則提前終結」微優化，但本質仍是平方級。