1. 题目与思路拆解1.1 题目读透最小覆盖子串到底在问什么最近在刷 LeetCode 热门 100 题时第 76 题最小覆盖子串让我卡了一晚上也让我彻底把滑动窗口这个技巧吃透了。作为一个经常在子串、子数组问题上翻车的选手我强烈建议所有准备算法面试的同学把这道题当作必修题因为它几乎囊括了滑动窗口最核心的难点窗口什么时候扩、什么时候缩、怎么高效判断覆盖。题目本身不算复杂给你一个字符串s和一个字符串t需要在s中找出包含t全部字符的最短连续子串并返回它。如果找不到就返回空字符串。注意这里说的是“包含全部字符”不是“包含t这个子串”所以顺序无所谓但有一个关键约束每个字符的数量也要满足要求。比如t AABC那s的子串里必须至少有两个A、一个B、一个C哪怕字符之间隔得很远也行。这题适合谁来刷准备算法面试的同学、想系统学滑动窗口的初学者、以及那些对双指针只能做“无重复字符最长子串”这种入门题、想进阶到“困难题”的人。它虽然被标记为 Hard但其实只要把滑动窗口的模型吃透代码不超过三十行。真正难的永远是思路而不是实现。1.2 暴力解法的困境滑动窗口为什么是对的方向如果说这道题有什么让人第一眼放松警惕的地方那就是看起来用一个双重循环枚举所有子串、再逐个检查是否覆盖t就能解决。但仔细算一下复杂度枚举所有起点和终点是O(n^2)每次检查覆盖要遍历t或者当前子串最坏是O(nm)整体冲到O(n^3)都不夸张。当s长度来到十万、百万级别这个算法直接当场去世。就算你优化检查过程O(n^2)依然扛不住长字符串。滑动窗口之所以是对的方向在于它用两个指针维护了一个“动态区间”让每个字符最多被访问两次右指针负责把新字符请进窗口左指针负责把不再需要的字符请出窗口。整个过程就像你在读一本很长的书要找一段包含所有关键词的段落。你会先看到一段大致覆盖所有关键词的文字然后试着删掉开头的几个字发现某个关键词没了就继续往后面读再补上再尝试删。这种“读一段、缩一段”的方式本质上就是滑动窗口。放到题目的语境里右指针每次向前移动一格让窗口包含更多的字符一旦窗口已经完整覆盖了t就开始移动左指针收缩窗口。收缩到“刚好不满足覆盖”为止然后继续移动右指针。因为每次右指针停在一个新位置时左指针都收缩到了当前最靠右的可行位置所以以该右端点为终点的所有窗口中你记录到的就是最短的一个。这样右指针遍历完整个s答案一定不会漏掉。2. 滑动窗口核心机制双指针与窗口收缩2.1 窗口的右扩与左缩两个指针各司其职滑动窗口最常见的实现是左闭右开区间[left, right)初始时两个指针都在 0。right每轮向右走一步表示把s[right]纳入窗口然后进入内层循环只要当前窗口已经覆盖了t就用left去收缩每次移出s[left]并更新答案。内层循环退出的条件是“刚好不覆盖”这时候再回去移动right继续扩展。有人会问为什么一定要等到“不覆盖”再停直接缩到最短再停不行吗实际上你无法在收缩过程中判断“现在是不是最短”因为后面可能还有更短的。所以常规做法是每次从覆盖状态收缩到临界状态并且在收缩过程中不断记录当前窗口长度取最小值。你收缩到不覆盖的那一步之前可能已经记录了很多个覆盖状态其中那个最短的就被保存了下来。我习惯用购物车来类比right是往购物车里塞商品left是把最早放进去的商品拿出来。你手里有一张购物清单t当购物车里每一种必需品数量都达标了就可以尝试把最前面的商品放回去但每放回一个都要看一眼清单上有没有缺东西。一旦缺了就停止归还继续往购物车里加新商品。2.2 如何判断“覆盖”计数表与匹配标记判断覆盖是整个算法的心脏。最笨的方法是把t的字符频次和当前窗口字符频次做比较每次都比较两个字典但这样会把O(1)的窗口状态判断变成O(k)其中k是t中不同字符数。如果t很长整体性能依然不够好。高效做法是维护两个频率表need记录t中每个字符还缺多少window记录当前窗口中每个字符出现了多少次。同时用一个整数matched表示“当前窗口中有多少个字符已经满足了need的要求”。只有当matched等于need中不同字符的数量时才说明窗口覆盖了t。这里有个特别容易踩坑的点matched的更新不是“每加入一个字符就加一”而是只有当window[c]刚好等于need[c]时才加一。比如need[A] 2窗口里A从 1 变成 2 的这一刻matched才加 1。继续加入第三个Amatched不再变化。反过来收缩窗口时只有当移除某个字符后它在窗口里的数量从“满足需求”变成“不满足需求”matched才减一。比如window[A]从 2 变成 1这时matched减 1。如果window[A]从 3 变成 2虽然数量变了但依然是满足需求的matched不应该减。用这种“计数表和匹配标记”的组合判断覆盖只需要O(1)时间。这也是滑动窗口题里最常见的性能优化手法几乎所有同类题目都能套用。2.3 关键参数窗口大小、need 与 have很多初学者学滑动窗口时喜欢背模板但背完还是写不对原因就是没搞清楚几个关键参数的含义。首先是need和window它们都是“字符 - 出现次数”的映射。其次是matched和needed前者是已经足额的字符类别数后者是t中总共需要足额的字符类别数。最后是min_len和start用来记录全局最优解的位置。窗口大小并不是直接维护一个变量而是通过right - left随时算出来的。由于区间是左闭右开[left, right)的长度就是right - left。在代码里你更新答案的时机应该是窗口满足覆盖条件、且准备移出左指针字符之前。这是整道题最容易被忽略的地方。如果等到matched已经小于needed了再更新窗口已经不覆盖了自然不能作为答案。有必要强调一下need和window都不需要额外初始化很多字符完全可以用 Python 的字典或者数组来实现。如果s中出现了t里没有的字符就不把它放进window也不参与matched的计数只是随着右指针“路过”窗口。3. 完整实现与踩坑实录3.1 标准实现Python 代码逐行拆解先给出一份完整的 Python 实现。我尽量保持代码简洁也方便在不同编辑器里直接跑def minWindow(s: str, t: str) - str: if len(s) len(t): return need {} for ch in t: need[ch] need.get(ch, 0) 1 needed len(need) window {} left right 0 matched 0 start 0 min_len float(inf) while right len(s): c s[right] if c in need: window[c] window.get(c, 0) 1 if window[c] need[c]: matched 1 right 1 while matched needed: if right - left min_len: min_len right - left start left d s[left] if d in need: if window[d] need[d]: matched - 1 window[d] - 1 left 1 return if min_len float(inf) else s[start:start min_len]从左到右看逻辑先过滤掉s比t短的情况然后构建need字典needed表示t中有多少种不同字符。右指针的扩展逻辑很简单但如果c不在need里就什么都不用做直接右移。收缩逻辑是精髓当matched needed时当前窗口覆盖了t于是先比较并更新最小长度然后准备移出s[left]。如果d在need中先检查window[d]是否刚好等于need[d]若是说明在移除这个字符后d的需求就不满足了因此matched减 1再真正执行window[d] - 1。这个顺序不能反反了你就会得到错误答案。3.2 细节推敲起点更新与最小长度比较很多人在自己实现时会把答案记录直接写成result s[left:right]然后把result跟当前的min_len比较最后返回result。这样写的隐患在于循环结束后的left和right指向的窗口大概率已经不是覆盖状态了因为最后一次移动右指针触发了内层收缩收缩结束后窗口恰好不覆盖。所以你必须用一个start变量单独记录“历史覆盖窗口的最小起点”再用min_len记录它的长度最后切片时用s[start:start min_len]。更新的时机也值得再强调一遍在matched needed时、移出左指针字符之前更新。因为此时窗口是合法的。如果放在移出之后窗口可能已经变得非法了如果放在右指针扩展之后可能窗口覆盖状态已经松弛记录的窗口不是最短。我自己第一次写的时候就是放在循环末尾结果答案总是少一个字符排查半天才发现是更新时机错了。还有一种常见写法是在收缩循环里先window[d] - 1再检查window[d] need[d]然后matched - 1。这个写法也能工作但前提是你已经用window.get(d, 0)做过保护。我的建议是统一用“先比较、再减”的顺序步骤更少也不容易把window[d]减成负数。3.3 我踩过的坑边界、空串、字符重复第一个坑是边界空串。s 或t 看起来简单但直接跑代码很容易报错。t 时need为空needed 0内层循环会一直在right尚未移动时触发导致left疯狂右移最后返回的却是整个s这个逻辑不符合题目要求。我在刷题平台提交时才发现题目默认t不为空但面试官可能会问。稳妥做法是在开头判断if not t: return 。第二个坑是字符重复。t AA时need中只有A一个键needed 1matched只要window[A] 2就变成 1。但如果你误以为needed应该等于t的长度也就是 2那matched永远不可能等于 2最后返回空串。这提醒我needed是不同字符的种类数不是字符总数。第三个坑是窗口里包含了大量无关字符。当s很长而t很短时window中可能只记录少数几个字符但如果每次都在window字典里get不存在的键代码也能跑只是性能稍差。更糟糕的是有人在收缩时把window[d]减成负数导致matched判断失效。解决办法就是只在d in need时才处理window[d]的更新。4. 常见问题与排查技巧实录4.1 典型问题速查表我在评论区见过不少初学者在同一个地方反复摔跤这里整理一个速查表方便你排查。现象可能原因解决办法总是返回空字符串s长度小于t或min_len从未更新开头判断长度检查matched是否逻辑错误返回的子串不是最短更新答案的时机不对可能在收缩后才记录把更新移动到matched needed时、左移之前子串缺失某个字符window[d]更新顺序错误导致matched提前减先判断window[d] need[d]再执行减一死循环left与right没有正确递增确认每次循环内right 1内层循环内left 1性能超时每次判断覆盖都遍历need或s切片使用matched整数标记避免用切片s[left:right]比较t为空字符串时结果异常题目边界没有处理在函数开头加入if not t: return 排查这类问题最好的方式不是盲目改代码而是加打印信息。我调试时会在right移动后、内层收缩前后分别打印left、right、window、matched、min_len。只要你盯着matched的变化很快就能看到是哪个字符导致覆盖状态没有被正确维护。4.2 复杂度分析与性能陷阱这道题标准解法的复杂度是O(n m)其中n len(s)m len(t)。因为左右指针都只向右移动每个字符最多被加入一次、移除一次。空间复杂度是O(k)k是字符集大小在 ASCII 范围内是一个常数所以通常也说成O(1)。但实际提交时还是会遇到性能差异。Python 字典虽然方便但常数较大。如果你的面试官要求极致的运行速度或者刷题平台卡得很紧可以考虑用数组替代字典def minWindow(s: str, t: str) - str: if len(s) len(t): return need [0] * 128 for ch in t: need[ord(ch)] 1 needed sum(1 for v in need if v 0) window [0] * 128 left right 0 matched 0 start 0 min_len float(inf) while right len(s): c ord(s[right]) if need[c] 0: window[c] 1 if window[c] need[c]: matched 1 right 1 while matched needed: if right - left min_len: min_len right - left start left d ord(s[left]) if need[d] 0: if window[d] need[d]: matched - 1 window[d] - 1 left 1 return if min_len float(inf) else s[start:start min_len]数组版本通过ord把字符转成 ASCII 码直接用下标访问省去哈希开销。但它只适合字符范围有限的情况比如 ASCII 字符串。如果题目涉及 Unicode 字符或者很长的扩展字符集还是字典更稳。另外要注意ord对中文字符会返回很大的数值这时候 128 的数组就不够用了。还有一个隐藏的性能陷阱很多人习惯在更新最小长度时用s[left:right]来做切片然后直接把这个切片存下来。Python 切片是一次字符串复制非常昂贵在大字符串上会带来额外开销。正确做法是用start和min_len记录位置最后返回时再切一次。这也是我在代码里反复强调start的原因。5. 滑动窗口的延伸从算法题到真实系统5.1 滑动窗口在其他场景的变形说句实话滑动窗口不只是算法题里的“套路”它在真实系统里也经常出现。比如网络传输里的滑动窗口协议控制发送方在不等待确认的情况下最多能发多少数据本质上也是一个“窗口”在时间轴上滑动。再比如信号处理里的滑动窗口滤波对连续采样的数据取一段窗口内的均值或中位数实时平滑噪声。还有数据库里常用到的滑动窗口聚合每隔一段时间统计最近五分钟的请求量。这些场景的内核都一样维护一个固定或动态的区间随着时间或数据流不断往前平移。如果你对滑动窗口有兴趣LeetCode 上还有几道题很值得连着刷第 3 题“无重复字符的最长子串”是滑窗入门第 438 题“找到字符串中所有字母异位词”和最小覆盖子串结构几乎一致第 567 题“字符串的排列”是固定窗口版第 239 题“滑动窗口最大值”则需要用单调队列配合。刷题时不要贪多一道一道来每道题都用手动模拟一遍窗口的移动过程比直接看题解有用得多。5.2 刷题心得与后续练习建议回到最小覆盖子串这道题我最大的收获不是背下了模板而是理解了“什么时候该收缩”和“怎么证明覆盖”。这两个问题想透了你就能自己推导出代码而不是靠记忆硬写。我建议大家拿到题先不要看题解尝试用购物车类比手动走一遍s ADOBECODEBANC, t ABC的过程。手动模拟的步骤很简单画两个标记一个left一个right每次右指针走一步在纸上记下window里各字符的数量同时盯着matched。当你第一次发现matched 3时窗口覆盖了ABC记下长度然后左指针开始右移每移一步观察matched是否变化直到它变成 2。然后再右移右指针继续。这个过程最好完整走一遍因为你对matched增减的理解会突然从“背代码”变成“真的懂”。这道题做完以后我建议你马上做一遍第 438 题感受一下几乎同样的代码、只是窗口长度固定时的差异。然后再做第 239 题你会发现滑动窗口加上单调队列后可以处理更难的场景。滑动窗口不是一个孤立的算法它是双指针思想的延伸也是后面很多复杂数据结构的起点。把最小覆盖子串啃下来你对“区间维护”这一类问题的信心会提升一大截。我个人在实际操作中的体会是刷算法题最怕只追求 AC然后忘了自己是怎么想出来的。LeetCode 76 这种题值得你花一晚上手动模拟、反复调试因为它能把“窗口收缩”这个思维刻进脑子里。如果你在面试中能把matched的原理讲清楚面试官基本不会再在这道题上为难你。最后再分享一个小技巧写代码前先在注释里写下三个关键词——right负责扩展、left负责收缩、matched负责判断覆盖。有了这个框架所有滑窗题都能立刻套上去。