1. 从一道“被面试官追着问”的题说起最小覆盖子串到底在考什么做 LeetCode 热题 100 的同学几乎都会在“滑动窗口”这个专题里撞见 76 题“Minimum Window Substring”中文一般叫“最小覆盖子串”。我刷题那阵子这道题前后做了三遍每过一段时间再翻出来都会发现新的理解盲区。它绝不是那种“背个模板就能过”的题而是把滑动窗口、哈希计数、边界处理、窗口收缩这几个高频考点全部揉在了一个题面里。先看题目本身给定一个字符串 s 和一个字符串 t要求在 s 中找出包含 t 全部字符的最短子串。这里的“包含”不是子序列而是字符数量要覆盖比如 t AABC那你在 s 里找的子串至少要包含两个 A、一个 B、一个 C。如果 s 中不存在这样的子串返回空串如果存在多个最短的返回任意一个即可。这道题在实际面试里受欢迎的原因很直接表面上是字符串处理本质上考察的是你能不能把“窗口内字符频次”这个状态维护清楚能不能想明白“收缩窗口”到底什么时候做、做到什么程度。很多人在暴力解法上浪费了大量时间也有不少同学能写出滑动窗口代码但一问“为什么窗口左端可以随便收缩”就开始支支吾吾。这篇博文就围绕这个题把滑动窗口的完整推导、代码实现、边界坑、变体扩展全部过一遍。无论是刚开始刷热题 100 的新手还是准备面试想系统梳理滑动窗口的求职者这篇都会对你有实际帮助。2. 思路选型暴力法的复杂度天花板在哪以及为什么必须用滑动窗口在给代码之前我建议先自己动手列一列暴力解法的时间复杂度。很多同学一看题目第一反应是枚举 s 的所有子串对每个子串统计字符频次再看是否覆盖 t。这个思路本身没错但算一笔账就清楚了s 长度为 n子串数量是 O(n^2)每个子串统计频次又需要 O(n)整体就是 O(n^3)。就算用前缀频次数组优化把子串统计降到 O(1)枚举 O(n^2) 依然是硬伤。当 n 到 10^5 级别这种解法直接超时没商量。2.1 滑动窗口为什么能优化掉一个数量级滑动窗口的核心思路是用两个指针 left 和 right 维护一个区间 [left, right]这个区间内的子串就是“当前窗口”。右指针负责扩展窗口把新字符纳入统计一旦窗口满足了覆盖条件就尝试移动左指针收缩窗口看能不能在保证条件成立的前提下把窗口缩得更短。整个过程左右指针都只往一个方向移动每个字符最多被右指针扫一次、被左指针扫一次整体时间复杂度 O(n)空间复杂度 O(k)k 是字符集大小。这里的关键认知是滑动窗口本质上是把“枚举所有子串”变成了“枚举所有可行的窗口状态”。我们不再关心那些明显不可能覆盖 t 的子串而是让窗口在“不满足覆盖条件”和“满足覆盖条件”两种状态之间切换。右指针负责从不满足推向满足左指针负责在满足的情况下尝试压缩。2.2 为什么不能用简单子串包含判断还有一个容易踩的误区有人会想先把 t 里每个字符在 s 中的出现位置记下来然后通过区间覆盖来求最小长度。这听起来有点像“合并区间”的思路但实际操作很麻烦因为 t 中同一个字符可能出现多次各个字符的位置也不是独立分布的区间之间互相制约很难直接合并。就算实现了处理重复字符的代码复杂度也不比滑动窗口低多少还容易出错。所以刷题阶段优先把这个模型的滑动窗口写法练熟性价比最高。3. 核心细节拆解窗口状态怎么维护条件怎么判定代码每一行在干什么我先给一个可直接运行的版本用的是 Java因为面试里写 Java 的人最多。如果你平时用 Python、C、Go核心逻辑完全一样只是语言语法不同。class Solution { public String minWindow(String s, String t) { if (s null || t null || s.length() t.length()) { return ; } int[] need new int[128]; int[] have new int[128]; for (int i 0; i t.length(); i) { need[t.charAt(i)]; } int left 0, right 0; int count 0; // 当前窗口已经“完整覆盖”的 t 中字符种类数 int required 0; // t 中不同字符的种类数 for (int i 0; i 128; i) { if (need[i] 0) required; } int minLen Integer.MAX_VALUE; int ansLeft -1; int ansRight -1; while (right s.length()) { char c s.charAt(right); have[c]; if (need[c] 0 have[c] need[c]) { count; } while (count required) { if (right - left 1 minLen) { minLen right - left 1; ansLeft left; ansRight right; } char lc s.charAt(left); have[lc]--; if (need[lc] 0 have[lc] need[lc]) { count--; } left; } right; } return ansLeft -1 ? : s.substring(ansLeft, ansRight 1); } }3.1 为什么用两个数组 need 和 have而不是一个 HashMap很多滑动窗口教程会用两个 HashMap一个记录 t 的需求次数一个记录窗口内的实际次数。用数组实现是更贴近底层的优化写法。ASCII 字符集一共 128 个默认题目输入是英文字母的话128 完全够用如果包含扩展字符可以改成 256。数组的好处是查询和修改都是 O(1)没有哈希函数开销也不存在扩容问题。对于这道题用数组是性能最优解而且代码可读性并不差。need[t.charAt(i)] 这个初始化过程本质上是在建立一个字典t 中每个字符需要多少个。比如 t AABC那么 need[A] 2need[B] 1need[C] 1。3.2 count 和 required 这两个变量是滑动窗口的“命门”这是整个代码里最容易被忽略、也最能体现是否真正理解滑动窗口的部分。required 是 t 中不同字符的种类数它在初始化时统计。count 是当前窗口内“已经满足数量要求”的字符种类数。举个例子t AABCrequired 3A、B、C 三种。假设当前窗口内 have[A] 2have[B] 1have[C] 0那么只有 A 和 B 分别达到了 need 的要求count 2。只有 count required 时窗口才满足覆盖条件。这里有一个细节特别容易出错判断条件 have[c] need[c]而不是 have[c] need[c]。为什么因为当 have[c] 第一次达到 need[c] 时说明这个字符已经“达标”了count 应该加一。如果继续增加have[c] 已经大于 need[c]说明窗口中该字符数量超出了需求这并不影响覆盖但 count 不应该再加。所以只在“等于”的那一刻让 count 自增。这个设计非常巧妙也经常被拿来考察候选人是否真正理解状态维护的本质。3.3 窗口收缩时 count 什么时候减一收缩窗口的代码是char lc s.charAt(left); have[lc]--; if (need[lc] 0 have[lc] need[lc]) { count--; } left;这里的逻辑和扩展时对称当某个字符被移出窗口后如果它的实际数量已经从“满足需求”掉到了“不满足需求”那么这个字符种类就不算达标了count 要减一。比如 need[A] 2窗口内原本 have[A] 2左指针移走一个 A 后 have[A] 1不满足需求了count 减一。但如果 have[A] 原来是 3移走一个变成 2依然满足需求count 不变。这就是为什么代码里用的是 have[lc] need[lc] 而不是 have[lc] need[lc] - 1其实两种写法在这个逻辑下效果一样但小于号更直观也不容易在连续收缩时出错。3.4 循环结构外层扩展、内层收缩是标准双指针模型while (right s.length()) 控制右指针遍历整个 s。在每次循环里先把右指针指向的字符纳入窗口然后马上检查是否满足了覆盖条件。如果满足就进入内层 while 循环反复收缩左指针并在每次收缩前记录当前窗口长度。这里要特别注意内层循环用了 while 而不是 if是因为收缩一次之后窗口可能依然满足覆盖条件那就应该继续收缩尽可能把窗口压到最短。比如 s ADOBECODEBANCt ABC第一次满足条件时窗口是 ADOBEC收缩左指针后可能会得到 DOBEC此时依然覆盖 ABC 吗不覆盖了因为 D、O、B、E、C 里没有 A。但如果窗口是 BAC收缩左指针后变成 AC依然覆盖 ABC 吗覆盖此时就应该继续收缩到 AC。while 循环保证了只要还能收缩就一路收缩到底。3.5 结果记录的时机边收缩边更新还是满足条件时更新我在代码里是在收缩过程中、每次进入内层循环时先判断当前窗口长度是否更短如果是就更新答案。这个顺序是刻意的因为内层循环刚开始时窗口一定是满足覆盖条件的而且还没执行收缩这个时候的窗口是“满足条件的最长子串”。随着 left 一步步右移窗口长度逐步缩短直到最后一次满足条件的窗口出现然后下一次收缩就会让 count 减一退出循环。所以内层循环里每次进入时记录答案一定不会漏掉最短的那个。有一个更省事的写法是在 count required 时直接记录然后再收缩。两种写法结果一样但“先进内层循环再记录”对初学者更友好因为它把“满足条件”和“记录答案”绑定在一起逻辑上不容易乱。3.6 处理找不到覆盖子串的情况题目要求找不到时返回空字符串。我的做法是把 ansLeft 初始化为 -1如果在整个遍历过程中一次都没进入内层循环说明 s 中没有任何子串能覆盖 t返回空串。这里用 ansLeft 是否等于 -1 作为标志而不是用 minLen 是否还是 Integer.MAX_VALUE两种都可以但 ansLeft 更直观。4. 实操全过程从暴力枚举到滑动窗口的逐步改造这一节我带你完整走一遍从读题、分析、写第一版代码到优化的过程。如果你刚开始接触这道题建议不要直接跳到最优解而是先动手把最笨的解法写出来然后分析瓶颈再一步步优化。这个过程比记住最终代码重要得多。4.1 第一版暴力子串枚举找到问题在哪最直观的暴力做法是这样枚举所有 left 和 right截取子串统计字符频次判断是否覆盖。示例代码如下public String minWindowBruteForce(String s, String t) { int n s.length(); int[] need new int[128]; for (char c : t.toCharArray()) need[c]; int minLen Integer.MAX_VALUE; String ans ; for (int left 0; left n; left) { for (int right left; right n; right) { int[] have new int[128]; for (int k left; k right; k) have[s.charAt(k)]; if (cover(have, need)) { if (right - left 1 minLen) { minLen right - left 1; ans s.substring(left, right 1); } break; } } } return ans; } private boolean cover(int[] have, int[] need) { for (int i 0; i 128; i) { if (have[i] need[i]) return false; } return true; }这个版本在 n 小的时候没问题但一旦 n 到 10^4 以上三个循环套在一起基本跑不动。我自己测试过n 10^4 时这个暴力版本耗时已经超过 1 秒n 10^5 时直接几分钟都出不来。刷题网站给的数据范围通常是 1 s.length, t.length 10^5这个复杂度是绝对过不了的。4.2 第二版优化统计过程用前缀频次数组既然每次都重新统计子串频次太慢可以预先计算一个前缀频次数组 prefix[i][c]表示 s 的前 i 个字符中字符 c 的出现次数。这样任意子串 [left, right] 的字符频次 prefix[right1][c] - prefix[left][c]单次统计从 O(子串长度) 降到 O(1)。但这里有个尴尬的问题枚举所有子串依然是 O(n^2)前缀数组只优化了统计部分。当 n 10^5 时10^10 次枚举依然不可行。所以这个优化方向不能解决根本问题只能作为中间思考的过渡。4.3 第三版引入滑动窗口用双指针维护状态滑动窗口能做到 O(n)本质上是把“每个子串都看一遍”变成了“每个字符最多进出窗口各一次”。右指针扩展窗口时我们只需要更新右指针位置的字符左指针收缩时只更新左指针位置的字符。其余中间字符完全不用重新统计。这个思路在实现上就是第 3 节的最终代码。我建议你在本地自己跑一下这个过程打印每个步骤的 left、right、count 和当前窗口亲眼看它怎么从不满足到满足再从满足收缩到打破条件然后再扩展。这个动态过程理解透彻了滑动窗口这一类题就通了。4.4 示例推演s ADOBECODEBANC, t ABC我来手动推演一遍经典用例帮助你把代码逻辑和实际窗口变化对应起来。初始化need[A] 1, need[B] 1, need[C] 1, required 3, count 0。right 0字符 Ahave[A] 1 need[A]count 1。窗口 A不满足右移。right 1字符 Dhave[D] 1need[D] 0count 不变。窗口 AD不满足。right 2字符 Ocount 不变。窗口 ADO不满足。right 3字符 Bhave[B] 1 need[B]count 2。窗口 ADOB不满足。right 4字符 Ecount 不变。窗口 ADOBE不满足。right 5字符 Chave[C] 1 need[C]count 3。窗口 ADOBEC满足条件进入收缩阶段。left 0窗口 ADOBEC长度 6记录。移除 Ahave[A] 0 need[A]count 2。窗口变为 DOBEC不满足退出内层循环。right 6字符 Ocount 不变。窗口 DOBECO不满足。right 7字符 Dcount 不变。窗口 DOBECOD不满足。right 8字符 Ecount 不变。窗口 DOBECODE不满足。right 9字符 Bhave[B] 2因为 have[B] ! need[B]count 还是 2。窗口 DOBECODEB不满足。right 10字符 Ahave[A] 1 need[A]count 3。窗口 DOBECODEBA满足进入收缩。左指针指向 D移除后 still count 3。窗口 OBECODEBA长度 9比 6 长不更新。移除 Ocount 不变窗口 BECODEBA。移除 Bhave[B] 1等于 need[B]count 不变窗口 ECODEBA。移除 Ecount 不变窗口 CODEBA。移除 Chave[C] 0 need[C]count 2退出收缩。right 11字符 Ncount 不变。窗口 ODEBA N不满足。right 12字符 Chave[C] 1 need[C]count 3。窗口 ODEBANC满足进入收缩。左指针一步步右移窗口从 ODEBANC 最终收缩到 BANC长度 4更新答案。遍历结束返回 BANC。这个推演过程能帮你理解一个关键点窗口在收缩时并不一定立刻打破覆盖条件而是可能连续移出多个字符直到某个关键字符数量不够了才停。这个特性决定了内层循环必须是 while而不能是 if。5. 常见问题与排查技巧实录写这道题时几乎每个人都会在下面的几个坑里摔一跤。我把它们整理成速查表方便你写完代码对照排查。症状可能原因解决办法返回空字符串但实际存在覆盖子串need 数组初始化遗漏 t 中字符required 统计错误检查 t 的遍历是否完整required 在初始化后应立即统计count 永远达不到 required更新 count 的条件写成了 have[c] need[c]改成 have[c] need[c]只有首次达标才自增内层 while 循环死循环左指针移动时未同步更新 have 和 count确认收缩时先更新 have[lc] 再判断是否需要 count--最后 left结果是最长子串而不是最短答案记录时机不对在每次收缩前记录当前窗口而不是在收缩后记录s 长度远大于 t 但性能极差滑动窗口实现里每次判断覆盖都遍历整个 need用 count required 判断不要每次扫数组中文或扩展字符导致数组越界默认 128 不够字符码超过 127用 HashMap 或把数组大小改为 256这些坑里我本人踩得最多的是 count 的更新条件。第一次刷的时候我用的是 have[c] need[c]结果 count 一会儿正常一会儿翻倍最后答案错得离谱。调试了很久才意识到count 的语义是“已达标的字符种类数”不是“已达标的字符总数”所以必须用等于而不是大于等于。另一个高频问题是如何判断“满足覆盖”。很多版本的题解会写一个 check 函数每次进入内层循环遍历所有字符。这在小数据量下没问题但在 n 10^5 时内层循环会被频繁触发每次 O(128) 的遍历也能接受因为 128 是常数整体依然是 O(128 * n)不会超时。但如果你用 HashMap 且每次遍历 all keys性能就完全不一样了。所以用 count 变量来把“判断是否覆盖”从 O(k) 降到 O(1)是更优雅的选择。排查工具方面我强烈建议你在本地加一段调试代码打印每个循环的 left、right、count、当前窗口。我自己在刷题时会写这样一个 debug 函数private void debug(int[] have, int[] need, int left, int right, int count, int required) { if (right - left 50) return; System.out.printf([left%d, right%d, count%d/%d, window%s]%n, left, right, count, required, s.substring(left, right 1)); }有了这个输出动态过程一目了然定位问题会快很多。一条很实用的经验是如果你发现 count 从来没达到 required先去看扩展窗口时的 if 条件如果你发现窗口一直能收缩但结果不对先去看记录答案的位置。6. 从最小覆盖子串出发滑动窗口题型的通用模板与变体扩展很多热题 100 的题目看起来千变万化实际上核心解题框架非常一致。我现在把最小覆盖子串抽象成一个通用模板以后再遇到类似的题可以直接套用骨架。6.1 滑动窗口通用代码骨架不管题目是找最短、最长、还是满足某个条件的子串大体都可以按下面的结构写int left 0, right 0; while (right s.length()) { // 1. 扩展窗口将 right 指向的字符加入窗口 add(s.charAt(right)); // 2. 收缩窗口当窗口满足题目条件时尝试收缩左边界 while (windowMeetsCondition()) { // 3. 记录答案通常在收缩前或收缩时记录 updateAnswer(); // 4. 缩小窗口移除 left 指向的字符 remove(s.charAt(left)); left; } right; }难点在于“窗口满足什么条件”和“答案在什么时候更新”。最小覆盖子串找的是最短可行窗口所以答案在收缩前更新如果题目找的是最长无重复子串答案通常会在收缩循环结束后更新。这两种模式对应着完全相反的最优解方向。6.2 与 LeetCode 热题 100 里其他滑动窗口题的横向对比拿 3 题“无重复字符的最长子串”来对比。那道题同样用两个指针但窗口条件变成了“窗口内没有重复字符”收缩的触发条件是“新字符出现重复”。代码里没有 need 数组而是用一个 set 或频率数组记录窗口内字符。一旦某个字符存在两次就不断移动左指针直到移除重复的那个。再比如 438 题“找到字符串中所有字母异位词”这题其实是最小覆盖子串的兄弟题。它的窗口条件是“窗口长度等于 t 的长度且窗口内字符频次与 t 完全一致”。因为窗口长度固定所以收缩条件变成了“当窗口长度超过 p 的长度时强制收缩”。这类变体比最小覆盖子串要简单因为不需要动态判断“是否覆盖”只需要固定长度 频次完全相等。还有一个常见变体是“最多替换 K 个字符得到的最长重复字符子串”对应 424 题。窗口条件是“窗口内出现次数最多的字符数量 K 窗口长度”含义是剩下的字符都可以通过替换变成同一种字符。这题在更新答案时用的是收缩之后的状态和最小覆盖子串的更新时机又不一样。看到这里你应该能体会到滑动窗口不只是模板而是要根据题目条件精确调整“状态”和“收缩时机”。6.3 工程应用层面滑动窗口思想在真实业务里的使用场景面试官喜欢问滑动窗口是因为它在实际业务中确实有广泛应用。比如日志分析里要找出最近一分钟内访问次数超过阈值的 IP就可以用一个时间窗口来滑动统计在流量控制里要统计每秒请求数用的也是类似的计数器 时间窗口模型。虽然业务场景的窗口通常基于时间而不是字符串下标但状态更新的核心思想完全一致。我工作后写过一个数据同步工具需要统计某个时间窗口内被修改过的记录数量本质上也是维护一个计数状态。每次新增记录就把它纳入窗口每次有记录过期就从窗口里移除。这个和最小覆盖子串的 count 维护逻辑几乎一模一样。所以刷这道题不只是为了面试而是真正能培养一种“区间状态动态维护”的思维习惯。7. 实际操作中的个人体会与扩展建议最后分享几个我在反复刷这道题过程中积累的体会不算什么高深理论但都是实打实对后续刷题有帮助的经验。第一不要只背模板要理解 count 这个变量设计的意义。你能不看代码用自己的话说清楚“什么时候 count 加一、什么时候 count 减一、为什么等于而不是大于等于”才算真正掌握了最小覆盖子串的解法。如果说不清说明还在背题。第二刷完这道题后建议立刻把“无重复字符的最长子串”“找到字符串中所有字母异位词”“最小窗口子序列”这组题一起刷了。它们共享同一个骨架但状态定义和收缩条件各有变化。我是先把最小覆盖子串刷透再横向刷这些变体整体的效率比单独刷题高很多。第三写代码时注意变量命名的表意性。count、required、need、have 这些名字不是随便起的它们直接对应了算法思维中的关键状态。很多面试者在白板上写代码时变量名取成 a、b、c、d等写到收缩逻辑的时候自己都看晕了。好的命名能显著降低出错概率。第四如果面试官追问“能不能把空间复杂度再优化”你可以提一下用 HashMap 而不是固定数组只有在字符集不确定时才有必要如果字符集已知且较小比如只有英文字母数组就是最优选择。还有一个进阶优化思路是用双指针加一个“剩余需求字符数”变量这样 count 都不用维护每个字符是否达标而是直接维护还缺多少个字符不过实现细节更绕面试时建议慎重使用容易把自己说乱。综合下来第 3 节的标准写法最稳也最好讲。如果想把这道题吃得更透还有一个小的扩展练习修改题目的返回值要求返回所有长度相同的最短覆盖子串。这需要你在更新答案时不能只记录第一个而是要用一个列表把所有满足最短长度的窗口都存下来。这个变体对理解“答案记录时机”帮助很大我试过之后对滑动窗口循环的理解明显更深了一层。这道题我在面试前刷了不下五遍每一遍都能发现之前理解不到位的地方。它不只是一道题而是一把钥匙帮你打开字符串双指针算法的大门。