題目描述:給定字串 s,找出不含重複字元的最長子字串的長度。
解題思路:滑動視窗法:維護左指標 left 和雜湊表(字元 → 最後出現索引)。右指標遍歷字串;當遇到重複字元時,將 left 移動到重複字元上次出現位置的下一個(跳過重複)。每步更新視窗最大長度。注意 left 只向右移動(不能向左縮退)。
時間複雜度:O(n) — 每個字元最多進出視窗各一次。
空間複雜度:O(min(n, |alphabet|)) — 雜湊表大小受字元集大小限制。
1. left = 0, maxLen = 0, lastSeen = {}
2. For right from 0 to n-1:
a. If s[right] in lastSeen and lastSeen[s[right]] >= left:
left = lastSeen[s[right]] + 1
b. lastSeen[s[right]] = right
c. maxLen = max(maxLen, right - left + 1)
3. Return maxLen嵌套迴圈 O(n²):對每個起點,擴展直至遇重複 — 邏輯簡單但低效。
集合逐一移除 O(n) 但常數較大:用集合而非字典,逐一從左移除直至重複消失 — 同漸近複雜度但常數不優。