LeetCode 76题解析：滑动窗口与哈希表实现最小覆盖子串

1. 题目解析与核心思路LeetCode 76题最小覆盖子串是算法面试中的经典高频题目也是Hot100题库中的必刷题目。题目要求给定一个字符串S和一个字符串T在S中找出包含T所有字符的最短连续子串。这道题完美结合了滑动窗口和哈希表两大核心算法思想是检验面试者双指针应用能力的试金石。1.1 问题定义与示例给定两个字符串S和T其中S是源字符串长度10^5级别T是目标字符集合长度≤100 要求返回S中包含T所有字符包括重复字符的最短连续子串。如果不存在则返回空字符串。示例 输入S ADOBECODEBANC, T ABC 输出BANC 解释BANC包含A、B、C且是满足条件的最短子串1.2 暴力解法分析最直观的解法是枚举所有可能的子串检查是否包含T的所有字符。对于长度为n的S子串总数是O(n^2)每个子串检查需要O(m)时间m为T长度总时间复杂度O(n^2*m)显然无法通过LeetCode测试。1.3 滑动窗口思想滑动窗口是处理子串/子数组问题的利器。基本思路用左右指针维护一个窗口[l, r]右指针扩展窗口直到满足条件左指针收缩窗口优化解记录满足条件的最小窗口对于本题的特殊性在于需要统计字符频率T可能有重复字符窗口需要包含T所有字符包括重复次数2. 算法实现与优化2.1 哈希表辅助统计使用两个哈希表分别记录needT中各字符出现次数目标频率window当前窗口中各字符出现次数关键判断条件 当window包含所有need中的字符且对应计数≥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 # 满足条件的字符数 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. 关键技巧与优化点3.1 有效字符过滤当S中存在大量不在T中的字符时可以先预处理S记录所有在T中出现字符的位置减少无效比较filtered_s [(i, c) for i, c in enumerate(s) if c in need]3.2 变量命名技巧使用有意义的变量名提升代码可读性valid已满足条件的字符数need_cnt还需要匹配的字符总数替代valid3.3 循环不变式维护在滑动窗口算法中必须确保每次右移right后window状态正确更新每次左移left前当前解已被记录移动left后window状态同步更新4. 常见错误与调试技巧4.1 典型错误案例忘记处理T中字符重复的情况错误仅检查字符是否存在正确需要检查字符出现次数窗口收缩条件错误错误valid len(t)正确valid len(need)考虑重复字符索引越界问题错误while left right时未检查边界正确添加保护条件4.2 调试打印技巧在关键位置添加调试输出print(fl{left}, r{right}, valid{valid}, window{dict(window)})4.3 测试用例设计必须包含的测试场景常规情况有解无解情况多个解存在T有重复字符S和T完全相同S和T都为空5. 同类题目拓展掌握最小覆盖子串后可以解决一系列滑动窗口变种题无重复字符的最长子串LeetCode 3字符串排列LeetCode 567找到字符串中所有字母异位词LeetCode 438最长湍流子数组LeetCode 978这些题目都可以使用类似的滑动窗口框架只需调整窗口移动条件和状态判断逻辑。关键心得滑动窗口问题的核心在于确定何时扩展窗口、何时收缩窗口以及如何高效维护窗口状态。建议先写出框架再填充具体条件。