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