LeetCode 經典題解：無重複字符的最長子串（C 語言滑動窗口 O(n) 實現）

LeetCode 經典題解：無重複字符的最長子串（C 語言滑動窗口 O(n) 實現）

題目：給定一字串，找出不含重複字符的最長子串長度。子串需連續（區別於子序列）。

• "abcabcbb" → "abc"，長度 3
• "bbbbb" → "b"，長度 1
• "pwwkew" → "wke"，長度 3

演算法思路：滑動窗口 + 字符位置記錄表

1. 維護一個滑動窗口 [start, i] 表示當前無重複子串。
2. 用長度 128 的整型陣列 table 記錄每個 ASCII 字符在當前窗口的出現次數（0/1/2）。
3. 遍歷字串，右擴窗口：
• 若字符首次出現（++table[c] == 1），當前長度 currlen++。
• 若字符重複（== 2），先更新最大長度，再左縮窗口：從 start 向右移動，清理計數，直到移除重複字符，更新 start = j+1。
4. 遍歷結束後再次更新最大長度並返回。

C 語言完整實現

int lengthOfLongestSubstring(char* s) {
    int maxlen = 0, currlen = 0;
    int table[128] = {0};  // ASCII 字符計數表
    int i, j, start = 0;

    for (i = 0; s[i] != '\0'; ++i) {
        unsigned char c = s[i];  // 避免負索引
        if (++table[c] == 2) {   // 發現重複字符
            if (currlen > maxlen) maxlen = currlen;
            // 左縮窗口，清理計數
            for (j = start; j < i; ++j) {
                if (s[j] == c) {
                    table[s[j]] = 1;  // 保留當前字符一次
                    start = j + 1;    // 新窗口起始位置
                    break;
                } else {
                    --currlen;
                    table[s[j]] = 0;
                }
            }
        } else {
            ++currlen;  // 無重複，窗口右擴
        }
    }
    if (currlen > maxlen) maxlen = currlen;
    return maxlen;
}

關鍵點解析

優化方向

• 用 last_pos[128] 直接記錄字符最後出現索引，發現重複時 start = max(start, last_pos[c] + 1) 一步到位，省去內層迴圈。
• 位運優化：若僅小寫字母，可用 32-bit 整數位圖替代陣列。

滑動窗口是處理「子串/子陣列約束問題」的通用利器，掌握其「右擴左縮、狀態維護」核心模板，能高效解決大類相關題目。