題目描述:給定字串 s 和整數 k,找出最多含 k 個不同字元的最長子字串長度。
解題思路:使用滑動視窗搭配雜湊表。維護左指針 left、右指針 right,以及一個計數表 freq 記錄視窗內每個字元的出現次數。右指針向右擴展時,將 s[right] 加入 freq。每當視窗內不同字元數超過 k(即 freq.size() > k),就從左側收縮:將 s[left] 的計數減一,若計數歸零則從 freq 中移除該字元,再右移 left。維持視窗合法後,以 right - left + 1 更新最大長度。由於每個字元最多被加入和移除一次,整體時間複雜度為 O(n)。邊界條件:若 k == 0 則直接回傳 0;若 k >= s.size() 則整個字串都合法。
時間複雜度:O(n) — right 和 left 各最多移動 n 次,雜湊表的插入、查詢、刪除均為 O(1) 平均,總操作為 O(n)。
空間複雜度:O(k) — 雜湊表 freq 最多同時存放 k+1 個字元(收縮前的瞬間),實際上有界於字元集大小(ASCII 為 O(1),Unicode 為 O(k))。
1. If k == 0, return 0.
2. Initialize left = 0, maxLen = 0, freq = empty map.
3. For right from 0 to n-1:
a. Add s[right] to freq (increment count).
b. While freq.size() > k:
- Decrement freq[s[left]].
- If freq[s[left]] == 0, remove s[left] from freq.
- Increment left.
c. Update maxLen = max(maxLen, right - left + 1).
4. Return maxLen.方法一:滑動視窗 + 雜湊表(最優解) — 如本題解,時間 O(n)、空間 O(k)。最直觀且高效的做法。
方法二:滑動視窗 + 有序映射(TreeMap) — 使用有序映射 map<char, int> 取代 unordered_map,在需要快速找到「最左側字元」時有優勢(可在 O(log k) 內找到最小索引的字元)。整體時間 O(n log k)、空間 O(k)。適合 k 固定且需要確定性效能的場景。
方法三:暴力枚舉 — 枚舉所有子字串,對每個子字串計算不同字元數。時間 O(n²) 或 O(n³)、空間 O(1) 或 O(n)。簡單但效率差,大輸入超時。
unordered_map 與 map 各有何取捨?