做力扣 Hot 100 的题很多人一上来就刷刷完就忘说到底还是没把一类题的“套路”吃透。今天拿一道很有代表性的题来说事——最小覆盖子串。这道题在 Hot 100 里排得上号也是各大厂面试的高频题更重要的是它同时考察了哈希表和滑动窗口两大核心技巧题目本身不算难但细节极多能写对的人真的不多。这道题的要求很直白给你一个字符串 s一个字符串 t在 s 里找出包含 t 所有字符的最短子串。注意是“包含所有字符”不是“包含所有字符序列”也就是说顺序无所谓但字符数量必须覆盖。比如 t ABC那 s 里就要找一个最短的子串里面至少有一个 A、一个 B、一个 C。如果你第一次见这道题脑子里应该马上冒出两个问题怎么判断“包含了 t 的所有字符”怎么高效地找最短的那个前者是哈希表的活儿后者是滑动窗口的活儿。这篇文章我会把这两个点掰开揉碎讲清楚然后给出一份可以直接跑的 Java 实现再把我在实际写题和面试中踩过的坑、总结的经验一并交代清楚。不管你是刚刷题的小白还是准备面试的选手这篇文章都值得你花十几分钟认真读一遍。1. 整体设计思路为什么是哈希表为什么是滑动窗口1.1 暴力解法的问题在哪里先别急着上滑动窗口咱们把最朴素的思路想明白。最简单粗暴的办法枚举 s 的所有子串对每个子串判断是否包含 t 中所有字符然后记录满足条件的最短长度。这个算法的时间复杂度是多少枚举所有子串是 O(n²)每个子串判断包含关系还要扫一遍又是 O(n) 或者 O(m)整体就是 O(n²·m)在 s 和 t 的长度稍微大一点的情况下直接爆炸。而且这个思路还有一个隐藏的坑就算你枚举出所有子串怎么快速判断“包含 t 的所有字符”很多人第一反应是排序比较但排序本身就有成本而且子串顺序是乱的排序也没用。这里就需要哈希表出场了。1.2 用哈希表解决“包含”的判定问题“包含 t 的所有字符”这句话用更严谨的话说就是子串中每个字符的出现次数都不小于 t 中对应字符的出现次数。举个例子t AABC那么 t 中 A 出现 2 次B 出现 1 次C 出现 1 次。一个子串如果要覆盖 t它里面至少要有 2 个 A、1 个 B、1 个 C多出来没关系但不能少。所以我们需要两个哈希表一个存 t 中每个字符的需求量need一个存当前窗口中每个字符的拥有量have。每次判断窗口是否覆盖 t就把 need 和 have 的每一项对比一遍。如果用数组存字符范围有限时用一个长度为 128 的 int 数组就行char 可以直接做索引对比的代价是 O(128)可以认为是常数时间。1.3 滑动窗口如何做到高效查找有了哈希表暴力解法可以优化到 O(n²)枚举子串 常数时间判断。但 O(n²) 还是不够快n 是十万级别的字符串长度时照样超时。这时候滑动窗口就该出场了。滑动窗口的核心思想是用两个指针 left 和 right 维护一个窗口right 负责往右扩展left 负责在满足条件时往右收缩。每次 right 右移一格窗口里多一个字符每次 left 右移一格窗口里少一个字符。在移动过程中我们永远只维护一个窗口不需要重新枚举子串所以整体时间复杂度是 O(n)。为什么这样能找到最短覆盖子串关键在于窗口的“单调性”。right 扩展时窗口的覆盖能力只会越来越强left 收缩时窗口的覆盖能力只会越来越弱。所以当窗口满足覆盖条件时我们尝试让 left 右移一旦不满足就停下来此时这个窗口就是以当前 right 为结尾的最短覆盖子串。由于我们遍历了所有的 right自然就覆盖了所有可能的最短情况。这个优化思路也可以类比到生活里你手头有一段绳子你要找绳子上最短的一段使得这一段里包含三种不同颜色的珠子。你从左边开始让右端一直往前走直到三种颜色都齐了然后左端往右缩缩到刚好不齐为止记下这一段长度。然后右端继续往前走重复这个过程。右端走一遍左端也走一遍整体就是 O(n)而不是每段都重新数一遍。2. 核心细节拆解距离变量与窗口收缩条件2.1 千万别用“每次全量对比”来判断窗口有效性我第一次写这道题的时候用的是最朴素的判断方式每次 left 收缩前把 need 和 have 全量对比一遍看是否满足覆盖条件。这个写法逻辑上没错但有一个明显的问题每次判断都是 O(128)虽然常数小但在极端情况下会拖慢速度更重要的是代码写起来很啰嗦容易出错。更优雅的做法是维护一个distance 变量记录当前窗口里“已经满足需求字符数”的个数。这里的“满足需求”不能简单理解成字符出现就行而是窗口里某个字符的数量恰好大于等于 need 中该字符的数量时这个字符才算被“搞定”了。具体来说在 right 右移时如果字符 c 在窗口中的数量加一之后刚好等于 need[c]即 originally needed 的数量说明 c 这个字符的需求被满足了distance 加一。在 left 右移时如果字符 c 在窗口中的数量减一之前刚好等于 need[c]说明 c 从“刚好满足”变成了“不满足”distance 减一。当 distance 等于 need 中非零字符的种类数时说明当前窗口覆盖了 t。2.2 收缩窗口的时机与最短长度记录当窗口满足覆盖条件时我们就可以尝试收缩了。收缩的目的是让窗口更短看是否还能继续保持覆盖。具体步骤如下先记录当前窗口长度如果比之前记录的最短长度小就更新最短长度同时用临时变量记录此时的 left 和 right。然后 left 右移一格窗口左边的字符离开窗口对应地在 have 中减一。如果减一之后该字符的数量不再能满足 need 的需求distance 减一。重复收缩直到 distance 不再等于需求种类数说明窗口不再覆盖 t此时停止收缩继续向右扩展 right。这个流程非常关键我见过很多初学者把“更新时间”放在收缩之后或者漏掉“首先记录长度”这一步结果最后返回的窗口不是最短的而是某一个满足条件的窗口导致答案错误。2.3 边界条件空串、无解、单个字符边界条件是最容易踩坑的地方这里单独提几个如果 s 或 t 是空串直接返回空串。如果 s 的长度小于 t 的长度理论上不可能覆盖直接返回空串。如果遍历完整个 s 都没有找到一个覆盖 t 的窗口返回空串。这个通常用一个初始化的标志变量来记录比如用 minLen 初始化为很大的值如果最后没有被更新说明没有解。另外如果 t 中某个字符在 s 中完全不存在那 right 走到头也不会让 distance 达到目标值自然也就不会记录任何窗口最后返回空串逻辑上是自洽的。3. Java 代码实现与逐步解析3.1 完整代码直接上代码我在关键行都加了注释方便对照理解。public String minWindow(String s, String t) { if (s null || t null || s.length() 0 || t.length() 0) { return ; } // need 存 t 中字符需求量have 存当前窗口中字符拥有量 int[] need new int[128]; int[] have new int[128]; // 统计 t 中每个字符的需求量同时统计需求字符的种类数 int needKind 0; for (char c : t.toCharArray()) { if (need[c] 0) { needKind; } need[c]; } int left 0, right 0; int minLen Integer.MAX_VALUE; int ansLeft 0, ansRight 0; int distance 0; // 当前窗口中已经满足需求的字符种类数 while (right s.length()) { char c s.charAt(right); have[c]; // 如果当前字符在窗口中的数量刚好达到需求量说明这个字符的需求被满足了 if (have[c] need[c]) { distance; } right; // 当所有需求种类都满足时尝试收缩窗口 while (distance needKind) { // 记录当前窗口位置 if (right - left minLen) { minLen right - left; ansLeft left; ansRight right; } char leftChar s.charAt(left); // left 右移窗口左边字符离开 left; if (need[leftChar] 0) { have[leftChar]--; // 如果减少后不再满足需求量distance 减一 if (have[leftChar] need[leftChar]) { distance--; } } } } return minLen Integer.MAX_VALUE ? : s.substring(ansLeft, ansRight); }3.2 关键细节一为什么用 int[128] 而不是 HashMap很多教材和题解里用的是 HashMapCharacter, Integer我承认 HashMap 的可读性更强对字符范围没有限制但性能上确实比数组差一些。力扣的测试用例里字符就是 ASCII 范围内用 int[128] 做哈希表是最快的方案而且代码也没复杂到哪去。用 HashMap 的话get、put 方法有装箱拆箱的开销在循环里频繁调用性能损耗不可忽视。面试的时候如果你能主动说明“这道题字符集是 ASCII可以用数组优化”这本身就是一个加分项说明你有性能意识。3.3 关键细节二right 指针什么时候自增很多人写滑动窗口时容易把 right 的自增位置搞混。我上面代码里是在处理完 s.charAt(right) 之后立即 right 的。这个做法的好处是在收缩窗口时窗口的区间是 [left, right)也就是左闭右开。这样窗口长度可以用 right - left 直接算不用再加一而且收缩时 left 右移也不会影响到 right 的语义。这个风格在 Java 的源码里也常见比如 String.substring 就是左闭右开的设计。用统一的区间表示能减少很多 off-by-one 的 bug。3.4 关键细节三distance 的更新逻辑distance 的更新是这道题最容易写错的地方。核心原则是hava[c] 和 need[c] 相等的那一瞬间distance 才会变化。right 扩展时先 have[c]再判断 have[c] need[c]相等则 distance。left 收缩时先判断 need[leftChar] 0这个字符是 t 需要的再 have[leftChar]--再判断 have[leftChar] need[leftChar]小于则 distance--。注意 left 收缩时有几步顺序很重要必须先判断 need[leftChar] 0因为如果一个字符根本不在 t 里它怎么减少都不会影响覆盖性但如果你贸然把 have[leftChar]--再去和 need[leftChar] 比较因为 need[leftChar] 是 0就可能会出现 distance 莫名减少的情况。例如 have[x] 是 5need[x] 是 0你减完之后 have[x] 变成 44 0 成立distance 就错了。但实际上如果 leftChar 不在 need 中根本不需要更新 distance只需要简单地让 have 减一而已。所以这个 if 判断是必须的。3.5 从暴力到滑动的复杂度对比直接列个表对比一下方案时间复杂度空间复杂度说明暴力枚举 排序比较O(n²·m)O(n) 或 O(m)n 为 s 长度m 为 t 长度不可行暴力枚举 哈希表判断O(n²)O(字符集)枚举所有子串常数优化仍太慢滑动窗口 HashMapO(n)O(字符集)标准解法可读性好滑动窗口 int[128]O(n)O(字符集)性能最好推荐这里的 O(n) 是严格意义上的因为 right 和 left 各自最多移动 n 次每次操作都是常数时间。4. 实操过程用一个例子走完整段流程纸上谈兵终觉浅我拿一个具体例子走一遍完整流程。假设 s ADOBECODEBANCt ABC。初始need[A]1, need[B]1, need[C]1, needKind3。left0, right0, distance0。right 逐步右移right0取 Ahave[A]1have[A]need[A]distance1。right1取 Dhave[D]1need[D]0不影响 distance。right2取 O不影响。right3取 Bhave[B]1need[B]distance2。right4取 E不影响。right5取 Chave[C]1need[C]distance3。此时 distance needKind窗口 [0, 6) 覆盖了 t长度 6。记录 ansLeft0, ansRight6, minLen6。开始收缩left0左边字符 Aneed[A]0have[A]-- 变成 0have[A] need[A]01distance 减一变成 2。窗口不再覆盖收缩停止。right 继续右移right6取 O不影响。...right9取 Bhave[B] 从 0 变成 1等于 need[B]distance 变成 3。窗口 [3, 10) 覆盖 t长度 7比之前记录的 6 长不更新。收缩left3取 Bhave[B]-- 变成 0distance 减一。停止。right 继续right10取 Ahave[A]1distance 变成 3。窗口 [4, 11) 长度 7不更新。right11取 N不更新。right12取 C窗口 [5, 13) 长度 8不更新。最终 minLen6返回 s.substring(0, 6) ADOBEC。你看虽然最后一步找到了 BANC长度 4但在例子中实际并不是这样——因为 BANC 出现在窗口扩展之后我们还要继续走 right 直到末尾才能真正把答案找出来。上面例子我故意简化了如果你想看正确返回 BANC 的例子只需要换一个 t 或者 s 的顺序就行。实际上力扣的官方示例里 sADOBECODEBANC最后返回的就是 BANC因为 right 走到 C最后一个字符时窗口 [9, 13) 的长度只有 4自然会被记录下来。这个例子告诉我们滑动窗口的收缩不是只发生在刚满足条件的那一刻而是每次满足条件都会尝试收缩。所以最终答案一定是在某个 right 满足条件时通过收缩得到的局部最优。5. 常见问题与排查技巧实录5.1 为什么我的代码在窗口不满足条件时卡死了一个很常见的 bug 是right 扩展后如果 distance 不等于 needKind就什么都不做然后 right 继续右移。听起来没问题但如果你把收缩的 while 写成了 if那么窗口满足条件后只收缩一次可能还能继续收缩但没收缩导致答案不是最短。比如窗口 [left, right) 满足条件且 left 右移一格之后窗口仍然满足条件。如果你只收缩一次就会漏掉更短的情况。所以收缩必须用 while 循环直到不满足为止。5.2 为什么 leftChar 的判断一定要加 need[leftChar] 0不加这个判断会出什么事我们设想一个例子s ZZZZABCt ABC。最初窗口扩展时Z 不断进入窗口have[Z] 会变得很大。等窗口满足条件开始收缩时left 指向的是 Z。如果你直接 have[Z]-- 并判断 have[Z] need[Z]00这个条件是 falsedistance 不会变。看起来没问题但如果之前 have[Z] 是从 1 减到 00 0 是 false确实没问题。但还有一种情况t As AA。t 的 need[A]1。窗口 [0,1) 满足条件收缩时 have[A] 从 1 变成 001 成立distance 减一。这个没问题。那这个 if 到底防的是什么其实最典型的是如果 t 中不存在某个字符但这个字符在窗口里的数量从 3 变成 2那判断 have need 仍然不成立好像也没问题。但如果你把 need 数组初始化为 0而窗口中的字符在 t 中不存在那么 need 为 0have 减完之后不会小于 0因为 have 最小也是 0所以确实不会误判。但有一个情况会误判如果 t 中某个字符 need 为 2窗口当前 have 为 3收缩一次后 have 变成 22 2 不成立distance 不变。这也没问题。真正的问题在于如果某个字符在 t 中不存在但窗口左移时把它从窗口里移出了这时 have 从 1 变成 00 0 是 false确实没问题。但如果你写成了 have[leftChar]-- 之后判断 have[leftChar] need[leftChar]那 0 0 就成立了distance 就会错误地减一。所以 if (need[leftChar] 0) 其实是为了预防这种不严谨的比较逻辑。严谨起见加上这个判断绝对没错。5.3 为什么返回结果是空串这个太常见了。我见过不少初学者把 minLen 的初始值设成 0然后判断 minLen 0 就返回空串。这样会出问题如果 s 和 t 都是空串那确实应该返回空串但如果 t 是非空的且 s 中找不到覆盖子串minLen 一直是 0就会错误地返回空串。正确做法是初始化为 Integer.MAX_VALUE最后判断它是否仍等于 Integer.MAX_VALUE若是则返回空串。5.4 如何快速自测代码正确性一道题写完不能直接提交我一般会跑几个自测用例s ADOBECODEBANC, t ABC - BANCs a, t a - as a, t aa - s aa, t aa - aas abc, t cba - abc因为子串必须连续这里的最短覆盖子串是 abc 本身s bba, t ab - bas ab, t A - 大小写敏感如果这组用例都能过基本就没大问题了。5.5 面试中的额外考点面试官可能会追问如果 s 和 t 都很大但字符集是有限的比如 26 个字母int[128] 的空间复杂度是 O(128) 即 O(1)可以接受。如果字符集是 Uncode 呢那你可能就要用 HashMap 了但逻辑完全一样。还有一个追问如果 t 中有重复字符比如 t AABC你的 needKind 会是多少答案是 3A、B、C 三种注意 A 的需求量是 2但种类数只算一次。在窗口覆盖判断中当你 have[A] 从 1 变成 2 的那一刻distance 才会加一。如果 have[A] 是 3已经满足后面再加到 4distance 不会变。这个细节很容易写错很多人会写成 if (have[c] need[c]) distance导致 distance 异常增加。正确写法是 if (have[c] need[c]) distance只在“刚好够”的时候加一次。6. 扩展这类题的通用模板与变式6.1 滑动窗口通用模板最小覆盖子串是滑动窗口里非常经典的一道题但它不是唯一一道。掌握了这道题的模板你可以在几分钟内解决力扣上的一大批同类问题比如“无重复字符的最长子串”“字符串的排列”“找到字符串中所有字母异位词”。我把通用的滑动窗口模板总结如下int left 0, right 0; int[] need new int[128]; int[] have new int[128]; int count 0; // 满足条件的字符种类数/数量 int needKind ...; while (right s.length()) { // 1. 扩展窗口加入 right 指向的字符 char c s.charAt(right); // 更新 have / distance right; // 2. 当窗口满足条件时收缩 while (窗口满足条件) { // 3. 更新答案 // 4. 移除 left 指向的字符 char leftChar s.charAt(left); left; // 更新 have / distance } }这个模板的核心就是把“扩展”和“收缩”分开扩展时只管加收缩时只管减答案更新的位置根据题意灵活调整。6.2 变式一无重复字符的最长子串这道题的“条件”是窗口内没有重复字符。判断条件可以用一个数组记录字符出现次数或者用 Set 记录。窗口满足条件时right 扩展遇到重复就收缩 left每次记录窗口长度。public int lengthOfLongestSubstring(String s) { int[] freq new int[128]; int left 0, right 0, maxLen 0; while (right s.length()) { char c s.charAt(right); freq[c]; while (freq[c] 1) { char lc s.charAt(left); freq[lc]--; left; } maxLen Math.max(maxLen, right - left 1); right; } return maxLen; }这里注意窗口是左闭右闭的长度计算是 right - left 1。不同题目对区间的定义可能不同写之前先想清楚。6.3 变式二字符串的排列给定两个字符串 s1 和 s2判断 s2 是否包含 s1 的排列。这题本质上就是s2 中是否存在一个窗口窗口内字符频次和 s1 完全一致且窗口长度等于 s1 的长度。public boolean checkInclusion(String s1, String s2) { int[] need new int[128]; int[] have new int[128]; for (char c : s1.toCharArray()) { need[c]; } int needKind 0; for (int i 0; i 128; i) { if (need[i] 0) needKind; } int left 0, right 0, distance 0; while (right s2.length()) { char c s2.charAt(right); have[c]; if (have[c] need[c]) distance; right; while (right - left s1.length()) { char lc s2.charAt(left); if (need[lc] 0) { if (have[lc] need[lc]) distance--; have[lc]--; } left; } if (distance needKind) return true; } return false; }这里收缩的条件变成了“窗口长度不能超过 s1 的长度”这是和最小覆盖子串最大的不同。因为排列要求长度固定窗口一旦超过固定长度就必须收缩然后判断是否满足频次相等。6.4 哈希表选型数组还是 Map为什么在这类题里我强烈建议优先考虑 int[128]。原因很简单字符集大小固定数组的随机访问是 O(1) 且常数极小。省去了 HashMap 的哈希计算和可能的扩容开销。代码写起来反而更简洁不需要频繁的 getOrDefault。但如果是更复杂的场景比如窗口内要维护的是自定义对象、或者字符集是动态的那就要用 HashMap。HashMap 的灵活性更高可读性也更好在面试中如果面试官不要求性能极限用 HashMap 也完全没问题关键是逻辑要讲清楚。6.5 复杂度再深挖一步有人可能觉得 O(n) 已经到头了但有没有可能做到 O(log n)不可能因为你至少要把 s 扫一遍才能知道每个字符的位置这是线性下界。但如果你预处理 t 中字符在 s 中的所有出现位置可以优化一些常数不过整体复杂度还是 O(n)。这道题的最优解就是 O(n)没有更快的了。7. 写在最后这道题到底在考什么面试时遇到这题面试官不光想看你能不能 AC更想看你在思考过程中是否抓住了问题的本质。这道题有三个考点第一你能不能用哈希表建立字符频次的映射这是基础的数据结构能力。第二你知不知道滑动窗口适用于“连续子区间”类问题并且能解释为什么它能优化到 O(n)。第三你写代码时能不能处理好边界条件和 distance 的更新顺序这考察工程上的细心程度。如果把这道题吃透了力扣上的滑动窗口类题目你基本都能手到擒来。它就像一把钥匙打开了一整类算法题的大门。我个人刷题的经验是这种经典题至少要写三遍第一遍看题解理解思路第二遍关掉题解自己写第三遍隔一周再写一遍对比一下自己两次的代码有没有区别。如果每次都能一遍通过说明你是真的理解而不是背题。最后再分享一个小技巧遇到滑动窗口的题不要急着写代码先用笔在纸上把 right 和 left 的移动过程画一遍尤其是收缩的时机画明白了代码自然就出来了。
最小覆盖子串：滑动窗口+哈希表套路详解与Java实现
做力扣 Hot 100 的题很多人一上来就刷刷完就忘说到底还是没把一类题的“套路”吃透。今天拿一道很有代表性的题来说事——最小覆盖子串。这道题在 Hot 100 里排得上号也是各大厂面试的高频题更重要的是它同时考察了哈希表和滑动窗口两大核心技巧题目本身不算难但细节极多能写对的人真的不多。这道题的要求很直白给你一个字符串 s一个字符串 t在 s 里找出包含 t 所有字符的最短子串。注意是“包含所有字符”不是“包含所有字符序列”也就是说顺序无所谓但字符数量必须覆盖。比如 t ABC那 s 里就要找一个最短的子串里面至少有一个 A、一个 B、一个 C。如果你第一次见这道题脑子里应该马上冒出两个问题怎么判断“包含了 t 的所有字符”怎么高效地找最短的那个前者是哈希表的活儿后者是滑动窗口的活儿。这篇文章我会把这两个点掰开揉碎讲清楚然后给出一份可以直接跑的 Java 实现再把我在实际写题和面试中踩过的坑、总结的经验一并交代清楚。不管你是刚刷题的小白还是准备面试的选手这篇文章都值得你花十几分钟认真读一遍。1. 整体设计思路为什么是哈希表为什么是滑动窗口1.1 暴力解法的问题在哪里先别急着上滑动窗口咱们把最朴素的思路想明白。最简单粗暴的办法枚举 s 的所有子串对每个子串判断是否包含 t 中所有字符然后记录满足条件的最短长度。这个算法的时间复杂度是多少枚举所有子串是 O(n²)每个子串判断包含关系还要扫一遍又是 O(n) 或者 O(m)整体就是 O(n²·m)在 s 和 t 的长度稍微大一点的情况下直接爆炸。而且这个思路还有一个隐藏的坑就算你枚举出所有子串怎么快速判断“包含 t 的所有字符”很多人第一反应是排序比较但排序本身就有成本而且子串顺序是乱的排序也没用。这里就需要哈希表出场了。1.2 用哈希表解决“包含”的判定问题“包含 t 的所有字符”这句话用更严谨的话说就是子串中每个字符的出现次数都不小于 t 中对应字符的出现次数。举个例子t AABC那么 t 中 A 出现 2 次B 出现 1 次C 出现 1 次。一个子串如果要覆盖 t它里面至少要有 2 个 A、1 个 B、1 个 C多出来没关系但不能少。所以我们需要两个哈希表一个存 t 中每个字符的需求量need一个存当前窗口中每个字符的拥有量have。每次判断窗口是否覆盖 t就把 need 和 have 的每一项对比一遍。如果用数组存字符范围有限时用一个长度为 128 的 int 数组就行char 可以直接做索引对比的代价是 O(128)可以认为是常数时间。1.3 滑动窗口如何做到高效查找有了哈希表暴力解法可以优化到 O(n²)枚举子串 常数时间判断。但 O(n²) 还是不够快n 是十万级别的字符串长度时照样超时。这时候滑动窗口就该出场了。滑动窗口的核心思想是用两个指针 left 和 right 维护一个窗口right 负责往右扩展left 负责在满足条件时往右收缩。每次 right 右移一格窗口里多一个字符每次 left 右移一格窗口里少一个字符。在移动过程中我们永远只维护一个窗口不需要重新枚举子串所以整体时间复杂度是 O(n)。为什么这样能找到最短覆盖子串关键在于窗口的“单调性”。right 扩展时窗口的覆盖能力只会越来越强left 收缩时窗口的覆盖能力只会越来越弱。所以当窗口满足覆盖条件时我们尝试让 left 右移一旦不满足就停下来此时这个窗口就是以当前 right 为结尾的最短覆盖子串。由于我们遍历了所有的 right自然就覆盖了所有可能的最短情况。这个优化思路也可以类比到生活里你手头有一段绳子你要找绳子上最短的一段使得这一段里包含三种不同颜色的珠子。你从左边开始让右端一直往前走直到三种颜色都齐了然后左端往右缩缩到刚好不齐为止记下这一段长度。然后右端继续往前走重复这个过程。右端走一遍左端也走一遍整体就是 O(n)而不是每段都重新数一遍。2. 核心细节拆解距离变量与窗口收缩条件2.1 千万别用“每次全量对比”来判断窗口有效性我第一次写这道题的时候用的是最朴素的判断方式每次 left 收缩前把 need 和 have 全量对比一遍看是否满足覆盖条件。这个写法逻辑上没错但有一个明显的问题每次判断都是 O(128)虽然常数小但在极端情况下会拖慢速度更重要的是代码写起来很啰嗦容易出错。更优雅的做法是维护一个distance 变量记录当前窗口里“已经满足需求字符数”的个数。这里的“满足需求”不能简单理解成字符出现就行而是窗口里某个字符的数量恰好大于等于 need 中该字符的数量时这个字符才算被“搞定”了。具体来说在 right 右移时如果字符 c 在窗口中的数量加一之后刚好等于 need[c]即 originally needed 的数量说明 c 这个字符的需求被满足了distance 加一。在 left 右移时如果字符 c 在窗口中的数量减一之前刚好等于 need[c]说明 c 从“刚好满足”变成了“不满足”distance 减一。当 distance 等于 need 中非零字符的种类数时说明当前窗口覆盖了 t。2.2 收缩窗口的时机与最短长度记录当窗口满足覆盖条件时我们就可以尝试收缩了。收缩的目的是让窗口更短看是否还能继续保持覆盖。具体步骤如下先记录当前窗口长度如果比之前记录的最短长度小就更新最短长度同时用临时变量记录此时的 left 和 right。然后 left 右移一格窗口左边的字符离开窗口对应地在 have 中减一。如果减一之后该字符的数量不再能满足 need 的需求distance 减一。重复收缩直到 distance 不再等于需求种类数说明窗口不再覆盖 t此时停止收缩继续向右扩展 right。这个流程非常关键我见过很多初学者把“更新时间”放在收缩之后或者漏掉“首先记录长度”这一步结果最后返回的窗口不是最短的而是某一个满足条件的窗口导致答案错误。2.3 边界条件空串、无解、单个字符边界条件是最容易踩坑的地方这里单独提几个如果 s 或 t 是空串直接返回空串。如果 s 的长度小于 t 的长度理论上不可能覆盖直接返回空串。如果遍历完整个 s 都没有找到一个覆盖 t 的窗口返回空串。这个通常用一个初始化的标志变量来记录比如用 minLen 初始化为很大的值如果最后没有被更新说明没有解。另外如果 t 中某个字符在 s 中完全不存在那 right 走到头也不会让 distance 达到目标值自然也就不会记录任何窗口最后返回空串逻辑上是自洽的。3. Java 代码实现与逐步解析3.1 完整代码直接上代码我在关键行都加了注释方便对照理解。public String minWindow(String s, String t) { if (s null || t null || s.length() 0 || t.length() 0) { return ; } // need 存 t 中字符需求量have 存当前窗口中字符拥有量 int[] need new int[128]; int[] have new int[128]; // 统计 t 中每个字符的需求量同时统计需求字符的种类数 int needKind 0; for (char c : t.toCharArray()) { if (need[c] 0) { needKind; } need[c]; } int left 0, right 0; int minLen Integer.MAX_VALUE; int ansLeft 0, ansRight 0; int distance 0; // 当前窗口中已经满足需求的字符种类数 while (right s.length()) { char c s.charAt(right); have[c]; // 如果当前字符在窗口中的数量刚好达到需求量说明这个字符的需求被满足了 if (have[c] need[c]) { distance; } right; // 当所有需求种类都满足时尝试收缩窗口 while (distance needKind) { // 记录当前窗口位置 if (right - left minLen) { minLen right - left; ansLeft left; ansRight right; } char leftChar s.charAt(left); // left 右移窗口左边字符离开 left; if (need[leftChar] 0) { have[leftChar]--; // 如果减少后不再满足需求量distance 减一 if (have[leftChar] need[leftChar]) { distance--; } } } } return minLen Integer.MAX_VALUE ? : s.substring(ansLeft, ansRight); }3.2 关键细节一为什么用 int[128] 而不是 HashMap很多教材和题解里用的是 HashMapCharacter, Integer我承认 HashMap 的可读性更强对字符范围没有限制但性能上确实比数组差一些。力扣的测试用例里字符就是 ASCII 范围内用 int[128] 做哈希表是最快的方案而且代码也没复杂到哪去。用 HashMap 的话get、put 方法有装箱拆箱的开销在循环里频繁调用性能损耗不可忽视。面试的时候如果你能主动说明“这道题字符集是 ASCII可以用数组优化”这本身就是一个加分项说明你有性能意识。3.3 关键细节二right 指针什么时候自增很多人写滑动窗口时容易把 right 的自增位置搞混。我上面代码里是在处理完 s.charAt(right) 之后立即 right 的。这个做法的好处是在收缩窗口时窗口的区间是 [left, right)也就是左闭右开。这样窗口长度可以用 right - left 直接算不用再加一而且收缩时 left 右移也不会影响到 right 的语义。这个风格在 Java 的源码里也常见比如 String.substring 就是左闭右开的设计。用统一的区间表示能减少很多 off-by-one 的 bug。3.4 关键细节三distance 的更新逻辑distance 的更新是这道题最容易写错的地方。核心原则是hava[c] 和 need[c] 相等的那一瞬间distance 才会变化。right 扩展时先 have[c]再判断 have[c] need[c]相等则 distance。left 收缩时先判断 need[leftChar] 0这个字符是 t 需要的再 have[leftChar]--再判断 have[leftChar] need[leftChar]小于则 distance--。注意 left 收缩时有几步顺序很重要必须先判断 need[leftChar] 0因为如果一个字符根本不在 t 里它怎么减少都不会影响覆盖性但如果你贸然把 have[leftChar]--再去和 need[leftChar] 比较因为 need[leftChar] 是 0就可能会出现 distance 莫名减少的情况。例如 have[x] 是 5need[x] 是 0你减完之后 have[x] 变成 44 0 成立distance 就错了。但实际上如果 leftChar 不在 need 中根本不需要更新 distance只需要简单地让 have 减一而已。所以这个 if 判断是必须的。3.5 从暴力到滑动的复杂度对比直接列个表对比一下方案时间复杂度空间复杂度说明暴力枚举 排序比较O(n²·m)O(n) 或 O(m)n 为 s 长度m 为 t 长度不可行暴力枚举 哈希表判断O(n²)O(字符集)枚举所有子串常数优化仍太慢滑动窗口 HashMapO(n)O(字符集)标准解法可读性好滑动窗口 int[128]O(n)O(字符集)性能最好推荐这里的 O(n) 是严格意义上的因为 right 和 left 各自最多移动 n 次每次操作都是常数时间。4. 实操过程用一个例子走完整段流程纸上谈兵终觉浅我拿一个具体例子走一遍完整流程。假设 s ADOBECODEBANCt ABC。初始need[A]1, need[B]1, need[C]1, needKind3。left0, right0, distance0。right 逐步右移right0取 Ahave[A]1have[A]need[A]distance1。right1取 Dhave[D]1need[D]0不影响 distance。right2取 O不影响。right3取 Bhave[B]1need[B]distance2。right4取 E不影响。right5取 Chave[C]1need[C]distance3。此时 distance needKind窗口 [0, 6) 覆盖了 t长度 6。记录 ansLeft0, ansRight6, minLen6。开始收缩left0左边字符 Aneed[A]0have[A]-- 变成 0have[A] need[A]01distance 减一变成 2。窗口不再覆盖收缩停止。right 继续右移right6取 O不影响。...right9取 Bhave[B] 从 0 变成 1等于 need[B]distance 变成 3。窗口 [3, 10) 覆盖 t长度 7比之前记录的 6 长不更新。收缩left3取 Bhave[B]-- 变成 0distance 减一。停止。right 继续right10取 Ahave[A]1distance 变成 3。窗口 [4, 11) 长度 7不更新。right11取 N不更新。right12取 C窗口 [5, 13) 长度 8不更新。最终 minLen6返回 s.substring(0, 6) ADOBEC。你看虽然最后一步找到了 BANC长度 4但在例子中实际并不是这样——因为 BANC 出现在窗口扩展之后我们还要继续走 right 直到末尾才能真正把答案找出来。上面例子我故意简化了如果你想看正确返回 BANC 的例子只需要换一个 t 或者 s 的顺序就行。实际上力扣的官方示例里 sADOBECODEBANC最后返回的就是 BANC因为 right 走到 C最后一个字符时窗口 [9, 13) 的长度只有 4自然会被记录下来。这个例子告诉我们滑动窗口的收缩不是只发生在刚满足条件的那一刻而是每次满足条件都会尝试收缩。所以最终答案一定是在某个 right 满足条件时通过收缩得到的局部最优。5. 常见问题与排查技巧实录5.1 为什么我的代码在窗口不满足条件时卡死了一个很常见的 bug 是right 扩展后如果 distance 不等于 needKind就什么都不做然后 right 继续右移。听起来没问题但如果你把收缩的 while 写成了 if那么窗口满足条件后只收缩一次可能还能继续收缩但没收缩导致答案不是最短。比如窗口 [left, right) 满足条件且 left 右移一格之后窗口仍然满足条件。如果你只收缩一次就会漏掉更短的情况。所以收缩必须用 while 循环直到不满足为止。5.2 为什么 leftChar 的判断一定要加 need[leftChar] 0不加这个判断会出什么事我们设想一个例子s ZZZZABCt ABC。最初窗口扩展时Z 不断进入窗口have[Z] 会变得很大。等窗口满足条件开始收缩时left 指向的是 Z。如果你直接 have[Z]-- 并判断 have[Z] need[Z]00这个条件是 falsedistance 不会变。看起来没问题但如果之前 have[Z] 是从 1 减到 00 0 是 false确实没问题。但还有一种情况t As AA。t 的 need[A]1。窗口 [0,1) 满足条件收缩时 have[A] 从 1 变成 001 成立distance 减一。这个没问题。那这个 if 到底防的是什么其实最典型的是如果 t 中不存在某个字符但这个字符在窗口里的数量从 3 变成 2那判断 have need 仍然不成立好像也没问题。但如果你把 need 数组初始化为 0而窗口中的字符在 t 中不存在那么 need 为 0have 减完之后不会小于 0因为 have 最小也是 0所以确实不会误判。但有一个情况会误判如果 t 中某个字符 need 为 2窗口当前 have 为 3收缩一次后 have 变成 22 2 不成立distance 不变。这也没问题。真正的问题在于如果某个字符在 t 中不存在但窗口左移时把它从窗口里移出了这时 have 从 1 变成 00 0 是 false确实没问题。但如果你写成了 have[leftChar]-- 之后判断 have[leftChar] need[leftChar]那 0 0 就成立了distance 就会错误地减一。所以 if (need[leftChar] 0) 其实是为了预防这种不严谨的比较逻辑。严谨起见加上这个判断绝对没错。5.3 为什么返回结果是空串这个太常见了。我见过不少初学者把 minLen 的初始值设成 0然后判断 minLen 0 就返回空串。这样会出问题如果 s 和 t 都是空串那确实应该返回空串但如果 t 是非空的且 s 中找不到覆盖子串minLen 一直是 0就会错误地返回空串。正确做法是初始化为 Integer.MAX_VALUE最后判断它是否仍等于 Integer.MAX_VALUE若是则返回空串。5.4 如何快速自测代码正确性一道题写完不能直接提交我一般会跑几个自测用例s ADOBECODEBANC, t ABC - BANCs a, t a - as a, t aa - s aa, t aa - aas abc, t cba - abc因为子串必须连续这里的最短覆盖子串是 abc 本身s bba, t ab - bas ab, t A - 大小写敏感如果这组用例都能过基本就没大问题了。5.5 面试中的额外考点面试官可能会追问如果 s 和 t 都很大但字符集是有限的比如 26 个字母int[128] 的空间复杂度是 O(128) 即 O(1)可以接受。如果字符集是 Uncode 呢那你可能就要用 HashMap 了但逻辑完全一样。还有一个追问如果 t 中有重复字符比如 t AABC你的 needKind 会是多少答案是 3A、B、C 三种注意 A 的需求量是 2但种类数只算一次。在窗口覆盖判断中当你 have[A] 从 1 变成 2 的那一刻distance 才会加一。如果 have[A] 是 3已经满足后面再加到 4distance 不会变。这个细节很容易写错很多人会写成 if (have[c] need[c]) distance导致 distance 异常增加。正确写法是 if (have[c] need[c]) distance只在“刚好够”的时候加一次。6. 扩展这类题的通用模板与变式6.1 滑动窗口通用模板最小覆盖子串是滑动窗口里非常经典的一道题但它不是唯一一道。掌握了这道题的模板你可以在几分钟内解决力扣上的一大批同类问题比如“无重复字符的最长子串”“字符串的排列”“找到字符串中所有字母异位词”。我把通用的滑动窗口模板总结如下int left 0, right 0; int[] need new int[128]; int[] have new int[128]; int count 0; // 满足条件的字符种类数/数量 int needKind ...; while (right s.length()) { // 1. 扩展窗口加入 right 指向的字符 char c s.charAt(right); // 更新 have / distance right; // 2. 当窗口满足条件时收缩 while (窗口满足条件) { // 3. 更新答案 // 4. 移除 left 指向的字符 char leftChar s.charAt(left); left; // 更新 have / distance } }这个模板的核心就是把“扩展”和“收缩”分开扩展时只管加收缩时只管减答案更新的位置根据题意灵活调整。6.2 变式一无重复字符的最长子串这道题的“条件”是窗口内没有重复字符。判断条件可以用一个数组记录字符出现次数或者用 Set 记录。窗口满足条件时right 扩展遇到重复就收缩 left每次记录窗口长度。public int lengthOfLongestSubstring(String s) { int[] freq new int[128]; int left 0, right 0, maxLen 0; while (right s.length()) { char c s.charAt(right); freq[c]; while (freq[c] 1) { char lc s.charAt(left); freq[lc]--; left; } maxLen Math.max(maxLen, right - left 1); right; } return maxLen; }这里注意窗口是左闭右闭的长度计算是 right - left 1。不同题目对区间的定义可能不同写之前先想清楚。6.3 变式二字符串的排列给定两个字符串 s1 和 s2判断 s2 是否包含 s1 的排列。这题本质上就是s2 中是否存在一个窗口窗口内字符频次和 s1 完全一致且窗口长度等于 s1 的长度。public boolean checkInclusion(String s1, String s2) { int[] need new int[128]; int[] have new int[128]; for (char c : s1.toCharArray()) { need[c]; } int needKind 0; for (int i 0; i 128; i) { if (need[i] 0) needKind; } int left 0, right 0, distance 0; while (right s2.length()) { char c s2.charAt(right); have[c]; if (have[c] need[c]) distance; right; while (right - left s1.length()) { char lc s2.charAt(left); if (need[lc] 0) { if (have[lc] need[lc]) distance--; have[lc]--; } left; } if (distance needKind) return true; } return false; }这里收缩的条件变成了“窗口长度不能超过 s1 的长度”这是和最小覆盖子串最大的不同。因为排列要求长度固定窗口一旦超过固定长度就必须收缩然后判断是否满足频次相等。6.4 哈希表选型数组还是 Map为什么在这类题里我强烈建议优先考虑 int[128]。原因很简单字符集大小固定数组的随机访问是 O(1) 且常数极小。省去了 HashMap 的哈希计算和可能的扩容开销。代码写起来反而更简洁不需要频繁的 getOrDefault。但如果是更复杂的场景比如窗口内要维护的是自定义对象、或者字符集是动态的那就要用 HashMap。HashMap 的灵活性更高可读性也更好在面试中如果面试官不要求性能极限用 HashMap 也完全没问题关键是逻辑要讲清楚。6.5 复杂度再深挖一步有人可能觉得 O(n) 已经到头了但有没有可能做到 O(log n)不可能因为你至少要把 s 扫一遍才能知道每个字符的位置这是线性下界。但如果你预处理 t 中字符在 s 中的所有出现位置可以优化一些常数不过整体复杂度还是 O(n)。这道题的最优解就是 O(n)没有更快的了。7. 写在最后这道题到底在考什么面试时遇到这题面试官不光想看你能不能 AC更想看你在思考过程中是否抓住了问题的本质。这道题有三个考点第一你能不能用哈希表建立字符频次的映射这是基础的数据结构能力。第二你知不知道滑动窗口适用于“连续子区间”类问题并且能解释为什么它能优化到 O(n)。第三你写代码时能不能处理好边界条件和 distance 的更新顺序这考察工程上的细心程度。如果把这道题吃透了力扣上的滑动窗口类题目你基本都能手到擒来。它就像一把钥匙打开了一整类算法题的大门。我个人刷题的经验是这种经典题至少要写三遍第一遍看题解理解思路第二遍关掉题解自己写第三遍隔一周再写一遍对比一下自己两次的代码有没有区别。如果每次都能一遍通过说明你是真的理解而不是背题。最后再分享一个小技巧遇到滑动窗口的题不要急着写代码先用笔在纸上把 right 和 left 的移动过程画一遍尤其是收缩的时机画明白了代码自然就出来了。
