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