滑动窗口算法解析：LeetCode最小覆盖子串实战

1. 问题背景与核心挑战这道题目来自LeetCode高频面试题库编号76题最小覆盖子串是字符串处理类问题的经典代表。给定字符串S和T要求在S中找到包含T所有字符的最短连续子串。例如S ADOBECODEBANCT ABC 正确输出应为BANC这类问题在实际工程中非常常见比如基因组序列匹配文档关键词高亮用户行为模式识别恶意代码特征检测2. 算法思路解析2.1 滑动窗口基本原理滑动窗口是处理子串/子数组问题的利器。基本框架包含初始化左右指针(left, right)表示窗口边界移动右指针扩大窗口直到满足条件移动左指针缩小窗口优化解重复2-3步直到遍历完成def slidingWindow(s: str, t: str) - str: left right 0 while right len(s): # 扩大窗口 window.add(s[right]) right 1 while valid(window): # 更新最优解 # 缩小窗口 window.remove(s[left]) left 12.2 本题的特殊处理本题需要三个关键数据结构need字典记录T中字符出现次数window字典记录当前窗口字符统计valid计数器统计满足条件的字符数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 0 min_len 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 min_len: start left min_len right - left d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return if min_len float(inf) else s[start:startmin_len]3. 复杂度分析与优化3.1 时间复杂度最优情况下O(n)每个字符最多被左右指针各访问一次哈希表操作视为O(1)3.2 空间复杂度O(|Σ|)Σ表示字符集大小英文字母场景为O(26)O(1)3.3 常见优化技巧预处理过滤先扫描S只保留出现在T中的字符及其索引边界剪枝当剩余未遍历长度小于当前最小窗口时可提前终止字符编码优化使用数组代替哈希表ASCII场景4. 实战注意事项边界条件处理T为空字符串S比T短S中不包含T所有字符测试用例设计test_cases [ (a, a, a), (a, aa, ), (ab, a, a), (aa, aa, aa), (ADOBECODEBANC, ABC, BANC) ]调试技巧打印窗口变化过程可视化valid计数变化检查哈希表状态5. 同类问题扩展无重复字符的最长子串LeetCode 3字符串的排列LeetCode 567找到字符串中所有字母异位词LeetCode 438最长重复子串LeetCode 10446. 工程实践建议内存优化对于超长字符串可改用生成器逐字符处理多语言实现掌握C/Java等语言的实现差异性能测试对比不同实现的运行时间单元测试覆盖各类边界情况实际编码时我习惯先用注释写出算法框架再填充具体实现。调试时特别要注意窗口收缩条件这是最容易出错的部分。建议在IDE中单步执行观察变量变化比直接提交更能发现问题本质。