聊到这道题的时候我脑海里冒出来的第一个画面是几年前在出租屋里对着编译错误发呆的夜晚。按钮一按红色的WA又来了。很多人第一次接触“最小覆盖子串”都是这种状态题面明明就一句话找包含目标串所有字符的最短子串但真上手写要么超时要么边界漏得跟筛子一样。而我那年刚好把刷题计划排到第九天题目编号又正好是76这个“九 76”就成了绕不过去的坎。这篇文章就把这道滑动窗口的招牌题彻底拆开从暴力解法的复杂度账本到计数表的精度设计再到那些一写就错的缩窗口细节。代码、反例、面试表达能给的都给你。适合正在系统刷题的新手也适合想把自己代码写得更干净的老手重温一遍。1. 题面拆解别把“覆盖”理解成“包含”1.1 输入输出的约定与边界先把题面说透。给定一个源串s和一个目标串t要求从s中找出最短的一个连续子串这个子串要“覆盖”t中的全部字符。这里的覆盖不是集合意义上的包含而是频次意义上的覆盖——t里如果出现了两个A那子串里至少也要有两个A。例子很经典s ADOBECODEBANCt ABC最短覆盖子串是BANC长度4。注意ADOBEC也是覆盖ABC的长度为6但不是最短。边界条件是如果s中根本不存在能覆盖t的子串返回空串。我见过不少新手第一反应是用Set 去判断覆盖把t拆成字符集合然后看子串是否包含这个集合。这个思路一遇到重复字符就崩了。t AABC的时候Set只记得A、B、C三个字符实际需要的A出现两次。这种需求用频次表比用集合更准确这也是后面整个算法的基石。1.2 暴力解的复杂度账本暴力做法是枚举所有子串。s的长度记作nt的长度记作m。子串起点有n种选择终点有n种共O(n^2)个子串。每个子串判断是否覆盖t最坏要把子串扫一遍再和目标频次比对复杂度O(nm)。总复杂度O(n^2 * (nm))约等于O(n^3)。n到1e4级别这个算法就已经跑不动了更别说LeetCode上真正的大样本。那为什么暴力这么慢根本原因是大量重复计算——同一个字符在不同起点终点组合中被反复扫描、反复比对频次没有任何复用。提示很多双指针题优化的本质是把“重复遍历”变成“增量更新”。滑动窗口正是这一思想的直接产物。2. 滑动窗口为什么是这道题的天选解法2.1 从双指针到窗口维护的直觉滑动窗口说白了就是两个指针left和right并且都只往右移动不回退。right每走一步窗口就多纳入一个字符当窗口满足覆盖条件时想办法移动left收缩窗口试图找到更短的合法区间。可以想象成一条拉链右指针负责把布料往前推拉到覆盖住所有需要的字符时暂停左指针再从后面把多余的布料缩回去直到再缩一个字符就会破坏覆盖为止。缩到极限后记录当前窗口长度然后右指针继续推进重复这个过程。这种思路之所以高效是因为每个字符最多被left访问一次、被right访问一次整体是O(n)级别的遍历。窗口内容的变化是增量式的不再从零扫描。2.2 计数表的设计两个哈希一个计数器代码实现的核心是三块目标需求表need、当前窗口表window、覆盖状态计数器valid。need负责记录t中每个字符的需求量。window记录当前窗口[left, right]范围内每个字符的实际出现次数。valid记录的是“当前窗口中已经满足需求量的字符种类数”。举例说明t AABCneed {A:2, B:1, C:1}一共有3种字符。当窗口里的A出现次数已经不少于2B不少于1C不少于1那么valid 3。三种字符全部满足覆盖成立。新手容易忽略的一点是valid记录的是“种类数”而不是“字符总数”。窗口里有5个A、0个B时A的计数已经满足但valid只能说A这一种达标可能只有1。不要把valid累加成所有字符的出现次数否则判断覆盖时会出现严重的逻辑错乱。2.3 窗口收缩的触发条件与更新时机收缩窗口的触发条件是valid need.size()也就是每个目标字符的频次都已达标。此时窗口是一个“合法覆盖”但未必最短。于是移动left把左侧字符移出窗口。每移动一位left窗口长度减少一位。移动之后如果窗口仍然覆盖说明还能继续缩短如果某个字符的频次掉到需求量以下覆盖被破坏停止收缩等待right继续扩展。这里藏着整道题最容易写错的一个地方更新答案的时机。应该在收缩过程中每移动一次left都检查当前窗口长度是否小于已记录的最小值。如果只在收缩结束之后更新一次可能会丢掉中间某一步更短的结果。实测下来我最初就是在这一步漏了案例。3. 可复现代码C实现与逐行解读3.1 核心代码#include string #include unordered_map #include climits using namespace std; class Solution { public: string minWindow(string s, string t) { if (s.empty() || t.empty()) return ; unordered_mapchar, int need, window; for (char c : t) need[c]; int left 0, right 0; int valid 0; int start 0, minLen INT_MAX; while (right s.length()) { char c s[right]; right; if (need.count(c)) { window[c]; if (window[c] need[c]) { valid; } } while (valid (int)need.size()) { if (right - left minLen) { start left; minLen right - left; } char d s[left]; left; if (need.count(d)) { if (window[d] need[d]) { valid--; } window[d]--; } } } return minLen INT_MAX ? : s.substr(start, minLen); } };3.2 每一步在干什么核心循环分两步。第一步是右指针扩展把新字符计入window。如果该字符是t需要的更新窗口计数。当window中的计数恰好等于need中的需求量时说明这一种类已经覆盖valid加一。第二步是左指针收缩当valid等于need.size()说明当前窗口已覆盖。立刻检查并记录长度——注意这里是先判断是否更新答案再移动left。为什么因为移动left之后窗口就不一定合法了你可能永远错过当前这个合法窗口的最短形态。移动left时先取出字符d若d在need中判断移除前window[d]是否等于need[d]。如果相等说明移除这一位会使该字符的需求从“满足”变成“不满足”valid要减一。然后再让window[d]减一。这个顺序极其重要先减计数再判断valid会出错。3.3 为什么用ASCII固定数组也可以上面代码用了unordered_map。很多C选手也喜欢用数组int window[128]和int need[128]在字符集是ASCII的场景下性能更好常数更小。但一旦字符集扩展到Unicode比如中文、表情符号固定数组就撑不住了。实际面试推荐先问清楚字符范围再决定用数组还是哈希表。能用数组时尽量用数组代码短、运行快也避免哈希函数带来的额外开销。同理Python和Java的哈希表用起来也方便但Java里HashMap对Integer的缓存比较有陷阱后面专门讲。4. 踩坑记录与现场排查实录4.1 常见的三个反例反例一s比t短直接返回空。很多实现里循环跑完才判断是否minLen初始值也能过但提前判断是更好的防御式写法。反例二t中存在s完全没有的字符。need的size永远不可能被valid追平循环结束时minLen保持初始值返回空串。正确性没问题但要注意不能拿“window中所有字符数量都不小于需求”这种条件替代valid判断否则会漏。反例三收缩窗口过度。我见过有同学在移动left时不是一位一位移而是直接跳到不再覆盖的地方导致结果不是最短。滑动窗口必须一位一位收缩每次收缩都检查答案。4.2 HashMap取值用比较的坑Java版本里如果写成window.get(c) need.get(c)当计数值比较小时Integer缓存可能导致结果偏差。小整数在-128到127之间会被缓存可能成立一旦计数超过127会比较对象引用直接失败。正确写法是intValue()比较或者equals()。C的map没有这个问题但Java的坑非常阴。我实际遇到的情况测试样例全都通过一个隐藏大样例计数超过127后结果全错。当时排查了很久最后定位到这不显眼的上。这就是典型的环境相关Bug。4.3 更新答案的时机不对导致漏解这是主观最容易踩的。假如在right扩展完、进入收缩循环之前更新一次答案拿到的是第一次合法时的窗口长度比如10。随后收缩某个更短窗口长度7出现时如果收缩循环里没有更新逻辑就会错过。只要把更新逻辑放进while (valid need.size())循环的开头先比较再收缩就不会漏。4.4 常见问题速查表问题原因解决方案结果返回空串s中不存在覆盖子串判断minLen是否为初始值结果不是最短更新答案时机不对收缩时每次移动left都检查valid计数错乱valid增减顺序错误先判断再修改计数Java版本大样本WAInteger缓存与比较改用equals或intValue覆盖判断出错用Set而非频次表用need和window两个计数表5. 从76题到一类滑动窗口题的迁移5.1 框架记忆法四步模板把滑动窗口的代码拆成固定模板很多题都能套right指针移动字符进入窗口更新窗口内部的数据结构判断当前窗口是否满足题设条件收缩left指针同时更新答案。76题的“条件”是覆盖所有目标字符用valid表示。换一道题条件可能变成“窗口内没有重复字符”“窗口内只包含两种水果”“窗口内字符种类不超过k”等。关键是找到那个代表“满足条件”的计数器或者状态量。5.2 无重复字符最长子串经典题“无重复字符的最长子串”条件变成窗口内不能有重复字符。于是用window记录字符出现次数。每次right扩展后若window[c]大于1说明有重复收缩left直到重复消失。这里valid的概念被一个布尔条件替代更简单一些但框架完全一致。这题值得注意的是求最长所以每次right扩展后都更新答案而不是等收缩过程。和76题正好相反。5.3 最多包含两个不同字符的最长子串这道题条件变成“窗口中不同字符数量 2”。维护window表同时维护一个变量count window中非零键的数量。right扩展时窗口新增字符若此前不存在count增加收缩left时若某字符计数归零count减少。其实和76题的valid有异曲同工之妙。迁移时你就发现valid和count本质上都是“当前窗口状态量”只要维护好这个状态量不同只是判断条件。这也是我后来刷题不再背模板、而是理解状态量的原因。5.4 长度最小的子数组另一道“长度最小子数组”给定数组和目标sum求满足总和sum的最短连续子数组。窗口条件变成“窗口内元素和 sum”。此时窗口数据结构只需要一个sum变量。right扩展时加值满足条件后收缩left每次收缩都减去left位置的值。代码写起来比76题更短但思路完全一致。6. 面试现场的表现与复盘建议6.1 拿到题先问什么真实面试中不要一上来就写代码。先和面试官确认三个关键点字符集范围是否是ASCII有没有要求返回所有满足条件的子串还是只需返回任意一条空串和不存在覆盖的边界怎么处理。这些问题能帮你避免用错数据结构同时展现你对边界条件的敏感度。有些面试官会在你说出“用哈希表记录频次”后就追问“这个valid变量为什么不能省”想清楚背后的逻辑valid存的是满足条件的字符种类数避免每次判断覆盖时去遍历哈希表比较这是一个典型的空间换时间优化也是滑动窗口这类问题能不能做到O(n)的关键之一。6.2 手写代码时的取舍手写代码命名要清晰left/right/valid/need/window比i/j/k直观得多。尽量用英文全称少写注释也能让阅卷者看懂逻辑。我习惯先把整体框架注释写清楚再填实现比如// 1. 初始化need和window // 2. right扩展 // 3. 满足条件时收缩left // 4. 更新最小长度这样即使中途写错也能更快定位。6.3 我自己复盘时的三个节奏点第一遍刷题重点在搞懂valid的增减时机建议手写一个t含重复字符的用例比如s aat aa走一遍全流程。第二遍刷题重点在默写框架把76题的代码闭卷写出来要求十分钟内完成。第三遍刷题重点在变体迁移同时写76题和“无重复字符的最长子串”对比两者的更新时机差异。我个人实际做了一遍又一遍之后最大的体会是这类题其实只有一个核心节奏先让窗口合法再让窗口最短。只要心里这个节奏不乱代码里的指针、计数器、更新逻辑都不会乱。最后再分享一个小技巧正式写代码之前在纸上画一组短的输入把left、right、valid的变化过程一步步标记出来。虽然看起来费时间但能省下调试时的大量时间。尤其是面试现场白板上画一条坐标轴把指针位置标出来讲题都会顺畅很多。
求解)
