1. 題目解析與核心思路LeetCode 76題最小覆蓋子串是算法面試中的經(jīng)典高頻題目也是Hot100題庫中的必刷題目。題目要求給定一個字符串S和一個字符串T在S中找出包含T所有字符的最短連續(xù)子串。這道題完美結合了滑動窗口和哈希表兩大核心算法思想是檢驗面試者雙指針應用能力的試金石。1.1 問題定義與示例給定兩個字符串S和T其中S是源字符串長度10^5級別T是目標字符集合長度≤100 要求返回S中包含T所有字符包括重復字符的最短連續(xù)子串。如果不存在則返回空字符串。示例 輸入S ADOBECODEBANC, T ABC 輸出BANC 解釋BANC包含A、B、C且是滿足條件的最短子串1.2 暴力解法分析最直觀的解法是枚舉所有可能的子串檢查是否包含T的所有字符。對于長度為n的S子串總數(shù)是O(n^2)每個子串檢查需要O(m)時間m為T長度總時間復雜度O(n^2*m)顯然無法通過LeetCode測試。1.3 滑動窗口思想滑動窗口是處理子串/子數(shù)組問題的利器。基本思路用左右指針維護一個窗口[l, r]右指針擴展窗口直到滿足條件左指針收縮窗口優(yōu)化解記錄滿足條件的最小窗口對于本題的特殊性在于需要統(tǒng)計字符頻率T可能有重復字符窗口需要包含T所有字符包括重復次數(shù)2. 算法實現(xiàn)與優(yōu)化2.1 哈希表輔助統(tǒng)計使用兩個哈希表分別記錄needT中各字符出現(xiàn)次數(shù)目標頻率window當前窗口中各字符出現(xiàn)次數(shù)關鍵判斷條件 當window包含所有need中的字符且對應計數(shù)≥need時窗口滿足條件from collections import defaultdict def minWindow(s: str, t: str) - str: need defaultdict(int) window defaultdict(int) for c in t: need[c] 1 left right 0 valid 0 # 滿足條件的字符數(shù) start, length 0, float(inf) while right len(s): c s[right] right 1 if c in need: window[c] 1 if window[c] need[c]: valid 1 while valid len(need): if right - left length: start left length right - left d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return s[start:startlength] if length ! float(inf) else 2.2 復雜度分析時間復雜度O(n)左右指針各遍歷一次字符串每個字符最多被訪問兩次右指針擴展、左指針收縮空間復雜度O(m)m為字符集大小ASCII最多1282.3 邊界條件處理需要特別注意的邊界情況S長度小于T時直接返回空T為空字符串時返回空S中不包含T所有字符時返回空多個解存在時返回第一個最小子串3. 關鍵技巧與優(yōu)化點3.1 有效字符過濾當S中存在大量不在T中的字符時可以先預處理S記錄所有在T中出現(xiàn)字符的位置減少無效比較filtered_s [(i, c) for i, c in enumerate(s) if c in need]3.2 變量命名技巧使用有意義的變量名提升代碼可讀性valid已滿足條件的字符數(shù)need_cnt還需要匹配的字符總數(shù)替代valid3.3 循環(huán)不變式維護在滑動窗口算法中必須確保每次右移right后window狀態(tài)正確更新每次左移left前當前解已被記錄移動left后window狀態(tài)同步更新4. 常見錯誤與調試技巧4.1 典型錯誤案例忘記處理T中字符重復的情況錯誤僅檢查字符是否存在正確需要檢查字符出現(xiàn)次數(shù)窗口收縮條件錯誤錯誤valid len(t)正確valid len(need)考慮重復字符索引越界問題錯誤while left right時未檢查邊界正確添加保護條件4.2 調試打印技巧在關鍵位置添加調試輸出print(fl{left}, r{right}, valid{valid}, window{dict(window)})4.3 測試用例設計必須包含的測試場景常規(guī)情況有解無解情況多個解存在T有重復字符S和T完全相同S和T都為空5. 同類題目拓展掌握最小覆蓋子串后可以解決一系列滑動窗口變種題無重復字符的最長子串LeetCode 3字符串排列LeetCode 567找到字符串中所有字母異位詞LeetCode 438最長湍流子數(shù)組LeetCode 978這些題目都可以使用類似的滑動窗口框架只需調整窗口移動條件和狀態(tài)判斷邏輯。關鍵心得滑動窗口問題的核心在于確定何時擴展窗口、何時收縮窗口以及如何高效維護窗口狀態(tài)。建議先寫出框架再填充具體條件。