Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：3. Longest Substring Without Repeating Characters（最長不重複子字串）

滑動窗口與 Hash Table 的經典應用

luk 收錄於 Leetcode
 約 1000 字 預計閱讀 5 分鐘 

題目描述

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

注意：子字串（substring）是連續的，子序列（subsequence）可以不連續。

範例： 

輸入：s = "abcabcbb"
輸出：3
解釋：最長不重複子字串是 "abc"，長度為 3

輸入：s = "bbbbb"
輸出：1
解釋：最長不重複子字串是 "b"，長度為 1

輸入：s = "pwwkew"
輸出：3
解釋：最長不重複子字串是 "wke"，長度為 3
注意答案必須是子字串，"pwke" 是子序列而不是子字串

核心概念理解

什麼是子字串？

  • 子字串（Substring）：必須是連續的字元序列
    • “abc” 是 “abcabcbb” 的子字串 ✓
    • “pwke” 不是 “pwwkew” 的子字串 ✗（中間跳過了字元）

問題關鍵

  1. 需要找到連續且不重複的字元序列
  2. 返回的是長度，不是子字串本身
  3. 當遇到重複字元時，需要調整窗口起始位置

解法一：暴力解法

思路

檢查所有可能的子字串，判斷是否有重複字元。

程式碼 

def lengthOfLongestSubstring(s):
    n = len(s)
    max_length = 0

    # 枚舉所有可能的起點
    for i in range(n):
        # 枚舉所有可能的終點
        for j in range(i, n):
            # 檢查 s[i:j+1] 是否有重複字元
            substring = s[i:j+1]
            if len(substring) == len(set(substring)):
                max_length = max(max_length, len(substring))
            else:
                break  # 遇到重複就不用繼續延伸

    return max_length

複雜度分析

  • 時間複雜度：O(n³)
    • 外層迴圈：O(n)
    • 內層迴圈：O(n)
    • set() 轉換和長度比較：O(n)
  • 空間複雜度：O(min(n, m))
    • m 是字元集大小（如 ASCII 是 128）
    • set 最多儲存 min(n, m) 個字元

優缺點

  • ✅ 簡單直觀
  • ❌ 效率極低，大數據會超時

解法二：滑動窗口 + Set

思路

使用雙指標維護一個窗口，確保窗口內的字元都不重複：

  1. 右指標不斷向右擴展窗口
  2. 當遇到重複字元時，左指標向右收縮窗口
  3. 持續記錄最大窗口大小

程式碼 

def lengthOfLongestSubstring(s):
    char_set = set()  # 記錄窗口內的字元
    left = 0
    max_length = 0

    for right in range(len(s)):
        # 當右指標的字元已存在，收縮左邊界
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        # 將右指標的字元加入窗口
        char_set.add(s[right])

        # 更新最大長度
        max_length = max(max_length, right - left + 1)

    return max_length

演算過程示例 

s = "abcabcbb"

初始：left=0, right=0, char_set={}, max_length=0

right=0, s[0]='a':
  'a' 不在 set
  加入 'a'，char_set = {'a'}
  max_length = max(0, 0-0+1) = 1

right=1, s[1]='b':
  'b' 不在 set
  加入 'b'，char_set = {'a','b'}
  max_length = max(1, 1-0+1) = 2

right=2, s[2]='c':
  'c' 不在 set
  加入 'c'，char_set = {'a','b','c'}
  max_length = max(2, 2-0+1) = 3

right=3, s[3]='a':
  'a' 在 set！需要收縮
  while 迴圈：
    移除 s[0]='a'，left=1，char_set = {'b','c'}
  加入 'a'，char_set = {'b','c','a'}
  max_length = max(3, 3-1+1) = 3

right=4, s[4]='b':
  'b' 在 set！需要收縮
  while 迴圈：
    移除 s[1]='b'，left=2，char_set = {'c','a'}
  加入 'b'，char_set = {'c','a','b'}
  max_length = 3

繼續... 最終 max_length = 3

複雜度分析

  • 時間複雜度：O(2n) = O(n)
    • 右指標遍歷一次：n 次
    • 左指標最多也移動 n 次
    • 總計最多 2n 次操作
  • 空間複雜度：O(min(n, m))
    • set 最多儲存 min(n, m) 個字元

解法三：滑動窗口 + Hash Table（最優解）

思路

使用 Hash Table 記錄每個字元最後出現的位置，可以直接跳過重複字元：

  1. 當遇到重複字元時，直接將左指標移到重複字元的下一位
  2. 不需要逐個移除字元

程式碼 

def lengthOfLongestSubstring(s):
    char_index = {}  # 記錄字元最後出現的位置
    left = 0
    max_length = 0

    for right in range(len(s)):
        # 如果字元已存在且在當前窗口內
        if s[right] in char_index and char_index[s[right]] >= left:
            # 直接跳到重複字元的下一位
            left = char_index[s[right]] + 1

        # 更新字元位置
        char_index[s[right]] = right

        # 更新最大長度
        max_length = max(max_length, right - left + 1)

    return max_length

演算過程示例 

s = "abcabcbb"

初始：left=0, right=0, char_index={}, max_length=0

right=0, s[0]='a':
  'a' 不在 dict
  char_index = {'a': 0}
  max_length = 1

right=1, s[1]='b':
  'b' 不在 dict
  char_index = {'a': 0, 'b': 1}
  max_length = 2

right=2, s[2]='c':
  'c' 不在 dict
  char_index = {'a': 0, 'b': 1, 'c': 2}
  max_length = 3

right=3, s[3]='a':
  'a' 在 dict 且 index[0] >= left[0]
  left = 0 + 1 = 1（直接跳到 'a' 的下一位）
  char_index = {'a': 3, 'b': 1, 'c': 2}
  max_length = max(3, 3-1+1) = 3

right=4, s[4]='b':
  'b' 在 dict 且 index[1] >= left[1]
  left = 1 + 1 = 2
  char_index = {'a': 3, 'b': 4, 'c': 2}
  max_length = 3

right=5, s[5]='c':
  'c' 在 dict 且 index[2] >= left[2]
  left = 2 + 1 = 3
  char_index = {'a': 3, 'b': 4, 'c': 5}
  max_length = 3

right=6, s[6]='b':
  'b' 在 dict 且 index[4] >= left[3]
  left = 4 + 1 = 5
  char_index = {'a': 3, 'b': 6, 'c': 5}
  max_length = 3

right=7, s[7]='b':
  'b' 在 dict 且 index[6] >= left[5]
  left = 6 + 1 = 7
  char_index = {'a': 3, 'b': 7, 'c': 5}
  max_length = 3

返回 3 ✓

複雜度分析

  • 時間複雜度：O(n)
    • 右指標遍歷字串一次
    • 每個字元最多被訪問兩次（一次加入，一次更新）
  • 空間複雜度：O(min(n, m))
    • Hash Table 最多儲存 min(n, m) 個鍵值對

為什麼需要檢查 >= left？ 

if s[right] in char_index and char_index[s[right]] >= left:

關鍵：確保重複字元在當前窗口內

範例：

s = "abba"

right=2, s[2]='b', left=0:
  'b' 在 index[1]，1 >= 0 ✓
  left 跳到 2

right=3, s[3]='a', left=2:
  'a' 在 index[0]，但 0 < 2 ✗
  不需要跳躍，因為 'a' 在窗口外

三種解法比較

解法時間複雜度空間複雜度優點缺點
暴力解O(n³)O(min(n,m))簡單極慢
滑動窗口+SetO(n)O(min(n,m))快速左指標可能多次移動
滑動窗口+HashO(n)O(min(n,m))最快邏輯稍複雜

程式碼技巧解析

1. 滑動窗口的本質 

窗口：[left, right]
- right 不斷向右擴展（探索新字元）
- left 根據條件向右收縮（維護有效窗口）

2. 窗口長度計算 

length = right - left + 1

範例：left=2, right=5
實際包含的索引：2, 3, 4, 5
長度 = 5 - 2 + 1 = 4 ✓

3. Set vs Hash Table

  • Set：只記錄元素是否存在
  • Hash Table：記錄元素 + 額外資訊（位置）
  • 本題用 Hash Table 可以獲取位置資訊，避免重複移動

4. Python 字典的預設行為 

# 安全的檢查方式
if s[right] in char_index:
    # 字元存在時的處理

# 也可以使用 get
last_index = char_index.get(s[right], -1)
if last_index >= left:
    left = last_index + 1

常見錯誤與注意事項

❌ 錯誤1：忘記檢查窗口範圍 

# 錯誤
if s[right] in char_index:
    left = char_index[s[right]] + 1  # 可能跳回去！

問題：字元可能在窗口外，left 不應該後退

❌ 錯誤2：窗口長度計算錯誤 

# 錯誤
max_length = max(max_length, right - left)  # 少算了 1

❌ 錯誤3：混淆子字串和子序列 

# 這是子序列，不是子字串
# "pwke" 可以從 "pwwkew" 得到（跳過一個 w）
# 但不是連續的，所以不算

❌ 錯誤4：Set 版本的左指標移動 

# 錯誤：一次移動太多
while s[right] in char_set:
    char_set.remove(s[left])
    left += 1
# 這是正確的！逐步移除直到沒有重複

延伸思考

1. 如果需要返回子字串本身？ 

def lengthOfLongestSubstring(s):
    char_index = {}
    left = 0
    max_length = 0
    result_start = 0  # 記錄最長子字串的起始位置

    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1

        char_index[s[right]] = right

        # 更新最長子字串的位置
        if right - left + 1 > max_length:
            max_length = right - left + 1
            result_start = left

    return s[result_start:result_start + max_length]

2. 如果限制字元集？ 

# 如果只有小寫字母（a-z），可以用陣列代替 Hash Table
def lengthOfLongestSubstring(s):
    char_index = [-1] * 26  # 26 個小寫字母
    left = 0
    max_length = 0

    for right in range(len(s)):
        idx = ord(s[right]) - ord('a')
        if char_index[idx] >= left:
            left = char_index[idx] + 1
        char_index[idx] = right
        max_length = max(max_length, right - left + 1)

    return max_length

3. 相關變化題

  • 至多包含 K 個不同字元：調整窗口條件
  • 至多包含兩個重複字元：允許部分重複
  • 固定長度窗口：檢查是否有重複

重要觀念總結

  1. 滑動窗口技巧：

    • 右指標探索，左指標維護條件
    • 適用於連續子陣列/子字串問題

  2. Hash Table 優化：

    • 記錄額外資訊（位置）可以減少操作
    • 用空間換時間的經典案例

  3. 邊界條件處理：

    • 檢查元素是否在當前窗口內
    • 避免指標後退

  4. 時間複雜度分析：

    • 雙指標不代表 O(n²)
    • 每個元素最多被訪問常數次仍是 O(n)

相關題目

  • LeetCode 76: Minimum Window Substring（最小窗口子字串）
  • LeetCode 159: Longest Substring with At Most Two Distinct Characters
  • LeetCode 340: Longest Substring with At Most K Distinct Characters
  • LeetCode 438: Find All Anagrams in a String（找所有字母異位詞）
  • LeetCode 567: Permutation in String（字串的排列）

練習建議

  1. 先實現 Set 版本，理解滑動窗口的核心思想
  2. 手動模擬幾個測試案例，理解 left 指標的移動邏輯
  3. 實現 Hash Table 版本，體會優化的效果
  4. 嘗試處理邊界情況：空字串、單字元、全部相同
  5. 挑戰變化題，鞏固滑動窗口技巧

這道題是滑動窗口技巧的經典入門題，掌握這個模式後，可以解決大量類似的子字串/子陣列問題！

更新於 2025-01-04 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmSliding-WindowHash-Table
返回 | 主頁
0%