如果你打开 LeetCode 的 Hot 100 题库切到“分类”视角会看到里面有个特别有意思的分组子串。别的分组动辄十几二十道题这个分组只有 4 道题但刷过的人都知道这 4 道题几乎覆盖了字符串和数组里所有跟“连续区间”相关的考法。我身边不少朋友刚刷到这一组时觉得“4 道题不是分分钟搞定”结果一上来就被 239 滑动窗口最大值和 76 最小覆盖子串卡了两三天。这篇文章就把这 4 道题揉在一起讲每道题的思路是怎么来的、标准代码怎么写、哪里容易写崩以及面试时面试官会怎么变着法子延伸。这篇文章适合三类人正在按 Hot 100 刷题准备面试的求职者、学过基础数据结构但还没形成“套路感”的中级学习者以及那些已经二刷三刷、却依然对滑动窗口边界细节模棱两可的人。子串这个专题讲究“套路成型、细节量多”把这 4 题吃透后面遇到任何连续区间、子数组、覆盖类问题你至少能立刻想到两条清晰的路径。1. 子串专题的整体认知为什么只放这 4 道题1.1 子串题到底在考什么子串、子数组、区间这三类问题本质上是一回事在给定的线性序列里找一个满足某种条件的连续片段。这里的“连续”是关键词它决定了你能用哪些方法也决定了暴力解的天花板。如果没有“连续”这个限制很多题会变成排列组合问题复杂度直接爆炸。而正是因为连续我们才能用前缀和来快速计算任意区间的总和用滑动窗口来维护一个不断变化的区间状态用单调队列来高效查询窗口内最值。换句话说子串题考察的不是某个高深数据结构而是你对“连续区间状态维护”这件事的熟练度。面试里子串题之所以高频是因为它很能区分基本功写出来不难但写出能在边界条件下不崩、能分析清楚复杂度、能面对变体迅速切换思路的人才是面试官想要的。1.2 四道题的分工一套组合拳这 4 道题在 Hot 100 里是固定组合我按刷题顺序排列如下题目核心考点主用数据结构刷题价值560. 和为 K 的子数组前缀和 哈希表HashMap建立区间和的快速计算意识438. 找到字符串中所有字母异位词固定窗口 频次比较频次数组/哈希表理解定长窗口的滑入滑出76. 最小覆盖子串双指针 可变窗口哈希表 计数器掌握窗口收缩的时机239. 滑动窗口最大值单调队列ArrayDeque窗口内最值的在线维护这个顺序不是随便排的。560 告诉你“连续区间求和”可以不用每次都重新算而是通过前缀和做 O(1) 查询438 则把“连续区间”这个概念搬到字符串上而且窗口长度是固定的相对好想76 在 438 的基础上把窗口变成可变难度提升一截但思路仍然是“先扩后缩”239 更进一层它不再只统计数量、频次而是要维护窗口的极值必须引入专门的结构。如果你按这个顺序刷会发现每个新题都是上一个思路的变体而不是凭空冒出新东西。1.3 一个让我很意外的点我第一次刷完这组题后最大的感触是并不是每道题都能用滑动窗口。560 那题很多人一看是“连续子数组”就想用双指针滑动窗口结果死活做不对因为数组里有负数窗口和不存在单调性。这个问题我后文会详细讲但先记住一句话看到连续子数组第一反应不应该是滑动窗口而是先判断数据是否支持窗口收缩。这个判断错误的代价我帮不少朋友排查过基本都能卡一晚上。2. 四道题逐题拆解思路、代码与易错点2.1 560. 和为 K 的子数组前缀和的魔法题目要求很简单给一个数组nums和一个整数k问有多少个连续子数组的和等于k。暴力做法是枚举每个起点 i 和终点 j然后用一个循环累加i..j的和复杂度 O(n³)。稍微优化一下可以在枚举终点时累加做到 O(n²)。但这里 n 的范围动辄 2 万甚至更多O(n²) 在面试中绝对过不了必须想 O(n) 的办法。这里的关键转换是前缀和。定义pre[i]表示数组前 i 个元素的和那么子数组nums[j..i]的和就等于pre[i1] - pre[j]。于是问题变成了找有多少对 (j, i)满足pre[i] - pre[j] k也就是pre[j] pre[i] - k。你看原来的问题是对“连续片段”求和现在变成了对“前缀和数组”做统计。我们可以一遍遍历用哈希表记录每个前缀和出现的次数每到一个位置 i查一下哈希表里有多少个pre[i1] - k累加入答案同时把当前前缀和的出现次数加一。给出 Java 实现import java.util.HashMap; import java.util.Map; public int subarraySum(int[] nums, int k) { MapInteger, Integer count new HashMap(); // 前缀和为0时出现1次代表空前缀 count.put(0, 1); int pre 0; int ans 0; for (int num : nums) { pre num; // 当前前缀和 pre要找目标 pre - k ans count.getOrDefault(pre - k, 0); count.put(pre, count.getOrDefault(pre, 0) 1); } return ans; }这里有几个极其容易写错的点。第一count.put(0, 1)不能省。假设nums [1, 2, 3],k 3遍历到pre 3时我们想找子数组从下标 0 开始的整个区间[1,2]它对应的是pre[j] 0的那个空前缀。如果不初始化 0你永远统计不到从头开始的子数组。第二先查询再更新顺序不能反。如果你先把当前前缀和放进哈希表再查询pre - k那么当k 0时你会把“当前这个位置本身”也当成一个答案多算一次。举个小例子nums [1],k 0正确结果是 0但先更新后查询会得到 1。第三这道题不能用滑动窗口。因为数组里有负数当窗口右端扩展使和变大时左端收缩却不一定使和变小可能负数让和继续增大也可能正数让和继续增大窗口和没有单调性你没法决定何时收缩。很多人第一反应是“和大于 k 就收缩”遇到负数就崩了。所以看到“连续子数组、定值”这类组合优先想前缀和而不是滑动窗口。2.2 438. 找到字符串中所有字母异位词固定窗口的掩护438 这道题说句实话单独拿出来不难但它是后面 76 题的跳板。题目是给定字符串s和p返回s中所有p的异位词子串的起始索引。所谓异位词就是两个字符串字符种类和数量都相同只是顺序不同。因为异位词长度必然等于p.length()所以窗口长度是固定的。我们只要能快速判断“当前窗口内字符频次”是否和p的字符频次一致就行。最直观的写法是用两个长度为 26 的数组记录字符频次一次滑动时只更新进窗口和出窗口的两个字符import java.util.ArrayList; import java.util.Arrays; import java.util.List; public ListInteger findAnagrams(String s, String p) { ListInteger res new ArrayList(); int sLen s.length(), pLen p.length(); if (sLen pLen) return res; int[] pFreq new int[26]; int[] winFreq new int[26]; for (char c : p.toCharArray()) pFreq[c - a]; // 初始化第一个窗口 for (int i 0; i pLen; i) { winFreq[s.charAt(i) - a]; } if (Arrays.equals(pFreq, winFreq)) res.add(0); // 滑动 for (int i pLen; i sLen; i) { winFreq[s.charAt(i) - a]; // 右边进一个 winFreq[s.charAt(i - pLen) - a]--; // 左边出一个 if (Arrays.equals(pFreq, winFreq)) res.add(i - pLen 1); } return res; }这个解法思路清晰复杂度 O(n * 26)几乎可以认为是 O(n)。但我在面试时更推荐另一种写法用一个count变量来记录“已经满足条件的字符种类数”避免每次Arrays.equals扫描整个数组。那种写法更装逼也更高效但代码细节更多。如果面试官让你优化你再拿出来。用count写法时我最常看到有人掉进的坑是出窗口字符的更新顺序反了。比如窗口内某个字符数量刚好等于目标数量时count要减一但如果你先把字符数减一再判断winFreq[d] pFreq[d]判断大概率不成立count就漏减了。正确顺序是先判断是否相等、再减少计数值。还有一个边界如果s.length() p.length()直接返回空列表不用进循环。这个判断放在最前面能省掉不少麻烦。2.3 76. 最小覆盖子串滑动的精髓在于收缩76 题是全组里最考验套路的一题。给定一个字符串s和一个字符串t要求在s中找出包含t全部字母的最短子串。注意t里可能有重复字符所以“覆盖”意味着每个字符出现的次数都要满足要求。这道题的核心是可变窗口 双指针右指针不断向右扩展直到窗口内包含了t的全部字符然后左指针开始收缩每次缩一个字符看窗口是否仍然满足覆盖条件并记录最短长度当窗口不再满足条件时右指针继续向右扩展。如此循环。我用一个计数变量count表示“还剩多少个字符需要匹配”。初始时count t.length()每次右指针移入一个t中需要的字符count就减一当count 0时说明窗口已经完全覆盖。下面是带注释的完整实现public String minWindow(String s, String t) { if (s.length() t.length()) return ; int[] need new int[128]; for (char c : t.toCharArray()) need[c]; int left 0, right 0; int count t.length(); int minLen Integer.MAX_VALUE; int start 0; while (right s.length()) { char c s.charAt(right); right; if (need[c] 0) count--; // 这个字符是 t 需要的 need[c]--; // 窗口中多了一个字符需求减一 while (count 0) { // 窗口已覆盖 t尝试收缩左边界 if (right - left minLen) { minLen right - left; start left; } char d s.charAt(left); left; need[d]; // 窗口少了一个字符需求加一 if (need[d] 0) count; // 如果这个字符变得“不够了”重新需要匹配 } } return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen); }这个写法初看有点反直觉我们对need数组中每个字符都做增减而不仅仅是t里有的字符。比如s里有字符z但t里没有z那么need[z]初始为 0右移时变成 -1左移时加回 0并不会影响count的判断。这种“把窗口内所有字符都纳入统计”的思路是很多滑动窗口模板的共同点好处是逻辑统一不需要额外判断字符在不在t中。这个题的易错点有两个。一个是count初始值到底设成什么。我看到有人按“需要满足的字符种类数”设count而不是按字符总数。如果用字符总数写起来直接跟t.length()挂钩不用额外统计种类更简洁。另一个是左边界收缩的时机。很多人以为每个循环都要收缩其实不是收缩只发生在count 0时。如果窗口还没有覆盖t你收缩了反而可能永远无法覆盖所以必须把“收缩”放在内层while里并且收缩之后要继续判断直到窗口刚好不再满足条件为止。我在面试中遇到过面试官追问“如果t里允许重复字符你的解法还能直接跑吗”这个问题其实是在考察哈希表计数的基本功。上面这个代码恰好天然支持重复字符因为need数组记录的是频次count记录的是剩余总需求。如果你用HashSet去重反而会写崩。所以刷这道题的时候一定要想清楚你记录的是“种类数”还是“总数”。2.4 239. 滑动窗口最大值单调队列的正确姿势最后一题是 239给一个数组nums和一个窗口大小k求出每个窗口的最大值。这题的直观做法是用优先队列大顶堆每次窗口移动时把新元素加进去但问题是堆顶可能已经在窗口外了你需要“延迟删除”。虽然能 AC但复杂度是 O(n log k)而且延迟删除的判断很容易写错。最优解法是单调队列而且必须用双端队列。单调队列维护的核心思想是窗口内所有“不可能成为最大值”的元素直接淘汰。比如窗口里有 5、3 两个元素现在来了个 4。3 比 4 小而且 4 比 3 晚进窗口、活得更久那么在 4 存在期间3 永远不可能成为最大值可以直接丢掉。5 虽然比 4 大但可能比 4 先滑出窗口所以要保留 5。实现时队列里存的是下标而不是值。因为只有存下标才能判断队首是否已经滑出窗口。import java.util.ArrayDeque; import java.util.Deque; public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] res new int[n - k 1]; DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 队尾所有小于等于当前元素的下标全部弹出 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offerLast(i); // 队首下标超出窗口范围时弹出 if (deque.peekFirst() i - k) { deque.pollFirst(); } // 窗口完全形成后每移动一次就记录一次结果 if (i k - 1) { res[i - k 1] nums[deque.peekFirst()]; } } return res; }这里我用了而不是含义是当新元素和队尾元素相等时队尾元素同样没有保留价值因为新元素更新、更晚过期用它能撑更久。如果你写成理论上也能过但队列里会多存一些相同值的旧下标性能稍差且逻辑上不够优雅。这个题还有一个容易被忽略的细节队首过期判断要在记录结果之前完成。如果先记录结果再判断过期在窗口恰好滑出队首元素的那一轮你可能会把旧的最大值多输出一次。我自己在第一次手写这个问题时就犯过“先取结果后清理”的错误单测跑出来结果是[6, 5, ...]排查了半天才发现是顺序问题。3. 实操记录一道子串题从审题到 AC 的完整复盘3.1 拿到题我先做什么我不建议一上来就看题解。以 560 为例拿到题第一步永远是确认数据范围。看一眼nums.length如果最大只有几百O(n²) 或许能行如果上万直接放弃暴力想优化。数据范围决定思路边界这是刷 LeetCode 养成的条件反射。然后是确认题目有没有“连续”这个限定以及数据里有没有负数。有负数意味着滑动窗口不可用你只能走前缀和。没有负数很多问题可以简化甚至可以二分但这是另一套思路了。3.2 从 O(n²) 到 O(n) 的思维跳跃过程以 560 为例我一开始写的是双层循环for (int i 0; i n; i) { int sum 0; for (int j i; j n; j) { sum nums[j]; if (sum k) ans; } }这个枚举思想其实是“以每个起点为锚点延伸终点”。它的问题在于每次枚举新的起点都要重新累加大量重复计算。前缀和存在的意义就是把“任意区间和”从 O(n) 降到 O(1)。想通了这一步代码反而很简短。我个人觉得刷这类题最有价值的时刻就是完成这个跳跃的瞬间当你能写出pre - k作为哈希表 key 去查答案时你对“空间换时间”这句话的理解会深一层。3.3 边界条件与测试用例写完后一定要在本地或编辑器里跑几个小 case。我常用的自测集合全是正数的常规数组比如[1, 2, 3]k3答案是 2[1,2]和[3]。包含负数和零的数组比如[1, -1, 0]k0答案是 2[1,-1]和[0]用来验证更新顺序。全部元素都相同的数组比如[1, 1, 1, 1]k2答案是 3用来验证重复计数。空数组和k0的组合用来验证初始化。我之前见过一个很难察觉的 bug前缀和哈希表更新和查询顺序写反了导致k0的时候答案总是多 1。通过上面第三个用例能立刻发现问题。3.4 关于周赛的延伸思考最近一次周赛里有一道子串统计题其实就是 438 的变体把目标字符串换成若干模式串再要求返回起始索引。用固定的窗口长度加上频次数组直接套模板就能过。这说明 LeetCode 的命题风格越来越偏向“经典套路 外壳包装”而热门的 Hot 100 子串专题恰好就是内核。另外偶尔会看到有人把“爱吃香蕉的狒狒”Koko Eating Bananas这道二分题和子串专题放在一起讨论。它们确实不在一个分类但二分法里检查“当前速度是否够用”的那个循环本质上也是一次连续区间的统计。等你把子串专题刷熟再去做二分验证类题目会感觉思路非常顺因为它们共享“线性遍历 条件判断”的底子。4. 常见问题与排查技巧实录4.1 前缀和哈希表更新顺序的坑这个前面已经提过但值得单列出来。规律是这样先算答案再更新状态。对应到 560就是先ans count.get(pre - k)再count.put(pre, ...)。对应到 76 题就是先判断need[c] 0再修改count。这个原则在几乎所有滑动窗口/前缀和问题里都成立。我自己刷题时会用红色标注这个顺序因为它是 Top 级易错点。4.2 滑动窗口无限循环的排查用双指针时最常见的 bug 是右指针在某种条件下没有前进导致死循环。正常逻辑里外层循环每次都让right但如果你在收缩时把left更新成了right或者更新到超过了右边界就会出现“左右指针互相追逐”的错乱。排查方法是打印每一步的left、right、count值。比如最小覆盖子串如果count初始值设置错误内层while(count 0)可能永远进不去右指针走到底直接结束返回空串。这时你要先检查count的更新逻辑而不是去看窗口长度判断。4.3 单调队列到底存索引还是存值239 这道题一定要存索引。存值的话你无法判断队首元素是否还在窗口内。每次移动后先清理队头过期索引再取队头作为答案。同样地清理队尾时用比用更优道理前面讲过。4.4 为什么有的题不能用滑动窗口这个属于“概念纠偏”。滑动窗口能工作的前提是窗口维护的性质具有单调性。比如“窗口内元素和最小覆盖”这种满足一定条件下可以收缩“窗口内最大值”这种来了新元素就可以淘汰旧元素。但“子数组和恰好等于 k”这个条件不具备单调性因为和变大变小的方向不受控制所以只能前缀和。面试时如果有人问“什么时候用前缀和什么时候用滑动窗口”可以给出一个粗糙但好记的标准如果窗口扩大时结果一定变好缩小时一定变差就用滑动窗口如果只是统计满足某个确切值的数量首选前缀和。4.5 面试延伸大字符串、外排序、在线数据库子串问题在真实业务场景里也常出现比如日志分析里找某个时间窗口内请求量最大的时间点、监控系统里找连续报警时间最长的窗口。面试官有时会问“如果s特别长不能一次性读进内存怎么办”本质上是在考你对外部存储和流式处理的理解。对于 239如果你面对的是流式数据单调队列依然适用因为每个元素只进出一次。对于 560如果数据太大且前缀和会溢出你可能要考虑分段哈希或者用long存储前缀和。这些超纲问题虽然不会在 Hot 100 里出现但理解了数组/字符串的窗口维护机制你就能在工程里迁移这套想法。为了让你对照排查时不迷糊我把这 4 道题最容易出错的位置汇总成一张表题目高频出错点一句话规避方法560初始化漏掉map.put(0,1)或先更新后查询先查答案再更新哈希表438出窗口字符的计数更新顺序反了先判断相等/减 valid再减少频次76count初始化错误或左右指针更新时机混乱明确 count 是“剩余总需求”只在覆盖时收缩239队列存值、过期判断放在取结果之后存索引先清理过期再记录答案5. 刷完这 4 道题之后的下一步按我个人刷题经验这 4 道题吃透之后可以顺手把这三类问题再过一遍二分查找、单调栈、以及常见的“双指针 哈希表”组合。子串专题特别适合用来建立“连续区间状态维护”的肌肉记忆它不会让你成为算法大师但足以让你在多数数据结构和算法面试中面对数组、字符串相关题时有一个非常明确的反应链能不能用固定窗口能不能用前缀和需不需要维护最值最后分享一个我自己的习惯我会把每道题的模板压缩成一份“最小可记忆版本”放在本地笔记里面试前只翻这个笔记。560 记住“前缀和 先查后更新”438 记住“固定窗口 频次数组”76 记住“need 计数 右扩左缩”239 记住“单调队列 存索引”。四个记忆点对应四道题面试时遇到再复杂的包装剥开来还是这四件事。