面试过的人多半有过这种体验算法题刷了不少但一到“子数组”“区间”这类问题脑子里能想起来的方法就只剩暴力枚举了。稍微好一点的知道该用双指针但拆开LeetCode 560、239、76这三道题就会发现它们虽然都长着一副“子数组题”的脸真正的考点却完全不在一个维度上——560的核心是前缀和与哈希表的组合239考的是滑动窗口与单调队列的配合76则是双指针窗口收缩的经典模板。这三道题放在一起刷其实就是把“子数组问题”这条线的最底层逻辑给串起来了。这篇文章不打算泛泛地讲概念而是把这三道题从头到尾拆开揉碎。你能看到每道题的暴力解是怎么一步步演化的、优化到底优化掉了什么、边界条件为什么会卡人、以及一些只有在实际提交时才会遇到的坑。不论是刚开始刷LeetCode、还是已经刷了百来题想整理思路这份笔记应该都能帮上忙。1. 这道专题到底在考什么先建立一个总体的解题坐标系1.1 滑动窗口不是银弹它有自己的边界条件很多人一看到“连续子数组”就想上滑动窗口这个直觉对了一半。滑动窗口本质上是双指针的一个特化应用它成立的先决条件是窗口的扩张和收缩之间存在单调性。也就是说右指针右移时窗口的某个属性单调变化左指针右移时这个属性反向单调变化只有在这种情况下双指针来回移动才不会有漏解的问题。拿LeetCode 239来说我们要求的是每个滑动窗口内的最大值这里窗口大小是固定的右指针和左指针都在单向向前移动这满足滑动窗口的物理结构。但问题在于我们要求“最大值”这件事但它随着窗口的收缩并不具备单调性——窗口变小最大值是可能变大也可能变小的这就没办法直接用普通的双指针维护窗口内某个值的信息。于是239引出了单调队列这个数据结构。相比之下LeetCode 76的“最小覆盖子串”就非常典型地满足了单调性当右指针扩张时窗口内覆盖目标字符的进度只增不减当左指针收缩时进度只减不增。所以它是一个标准的双指针滑动窗口模板题。而LeetCode 560就更特殊了它虽然叫“和为K的子数组”但数组中又有正数又有负数窗口的“和”属性既不随扩张单调递增也不随收缩单调递减。这种时候滑动窗口的指针移动策略直接失效必须换成前缀和加哈希表的思路。1.2 子数组问题常见的解法栈把上面说的整理一下子数组类问题其实有一条相对清晰的解法栈做题的时候可以按这个顺序去试如果没有单调性暴力枚举所有子数组是保底方案一般会超时但能帮你验证思路。如果窗口扩张/收缩时属性单调变化优先考虑双指针滑动窗口。如果数组里有负数、要求的是某种累加值恰好等于目标前缀和通常配合哈希表是通用解法。如果窗口内需要快速获得最大值/最小值堆和单调队列是两个主力数据结构通常更偏向单调队列。这个坐标系建立起来以后再去看LeetCode 560、239、76这三道题顺序就清晰很多——它们分别踩在“前缀和”“单调队列”“双指针”这三个技术点上。后面三章我按这个顺序逐一拆解。2. LeetCode 560和为K的子数组前缀和的活用才是题眼2.1 暴力解为什么慢慢在哪些计算被重复了题目描述很简单给定一个整数数组 nums 和一个整数 k你需要找到该数组中和为 k 的连续子数组的个数。数组长度最高能到 2 万数值范围是正负 1000 以内。最暴力的思路当然是枚举所有起点和终点计算区间和然后逐一比对。三层循环的写法一定是超时的改进一点固定起点向右扩张终点用累加的方式维护区间和这样也能把复杂度压到 O(n^2)。但数据量一大O(n^2)依然是噩梦LeetCode上不少题解的评论区里都能看到这种提交卡在超时边缘的案例。暴力解法慢的核心在于我们反复地从头计算了很多区间和。例如你算过 nums[0..5] 的和又在算 nums[1..5] 的和时把 nums[1]...nums[5] 又加了一遍。这些重复计算本来可以避免——只要提前算好每个位置的前缀和任意区间 nums[i..j] 的和就能用 prefix[j1] - prefix[i] 一步算出。2.2 前缀和公式推导和哈希表优化的关键一步前缀和的定义是prefix[i] 表示 nums 前 i 个元素的和特别地prefix[0] 0。于是任意区间 [i, j) 的元素和等于 prefix[j] - prefix[i]这里我用的是左闭右开写法方便后面处理。题目要求的是“有多少个子数组的和等于 k”也就是寻找有多少对 (i, j) 满足 prefix[j] - prefix[i] k。把这个式子稍微变一下形prefix[i] prefix[j] - k注意看等号右边j 是当前扫描到的位置prefix[j] 是已知的k 是固定不变的那么等号右边就是一个定值。换句话说当我们扫描到位置 j 时只要知道前面有多少个位置 i 的 prefix[i] 等于这个定值就能一次性算出以 j 结尾的子数组中有多少个满足条件。有了这个数学变形代码就可以用一次遍历实现了维护一个哈希表key 是前缀和value 是该前缀和出现的次数。每扫描到一个新位置就先用 prefix[j] - k 去哈希表里查一查次数再把当前前缀和存进哈希表。这里有一个非常容易被新手搞错的细节为什么要先查哈希表、再把当前前缀和存进去因为我们要找的是“以当前位置为结尾”的子数组子数组的起点必须严格在当前终点之前。如果先把当前 prefix[j] 存进去再查就可能把长度为零的子数组也当成合法答案了造成重复计数。2.3 完整代码实现与边界条件分析下面是Java版本的完整实现也是我在LeetCode上最终提交通过的版本class Solution { public int subarraySum(int[] nums, int k) { // key: 前缀和, value: 出现次数 MapInteger, Integer prefixSumCount new HashMap(); // 前缀和为0的情况默认出现一次对应空数组 prefixSumCount.put(0, 1); int prefixSum 0; int answer 0; for (int num : nums) { prefixSum num; // 如果存在 prefixSum - k 的前缀和说明中间这段区间和为 k answer prefixSumCount.getOrDefault(prefixSum - k, 0); // 记录当前前缀和出现的次数 prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) 1); } return answer; } }这个代码里有几个边界点值得展开说一下为什么初始化时要放一个(0, 1)因为前缀和数组里本来就包含prefix[0] 0表示一个元素都没有的“空前缀”。这样假设的好处是当某个位置的前缀和恰好等于 k 时prefixSum - k 0能直接匹配到这个初始记录把“从头开始到当前位置”的整个子数组算进去。数组中有负数和零时前缀和不一定是单调递增的同一个前缀和值可能反复出现多次所以哈希表里要记录的是“出现次数”而不是“是否出现过”。这是这道题和“两数之和”写法上最大的区别。答案的计数范围可能很大题目里没有说明模数所以用 int 就能过但如果你追求严谨了解极端输入可能导致 int 溢出也值得留意。就本题的数据范围来说int 是够用的。2.4 从这道题延伸出去的变体560 的变体非常多掌握了前缀和加哈希表后很多题都是同一个灵魂换不同的皮如果题目要求“和为 K 的子数组的数量中总长度最小是多少”那要在哈希表里维护前缀和对应的最早出现位置而不是次数。如果题目要求“能不能找到一个和为 K 的子数组”那可以用 HashSet 替代 HashMap一旦匹配上直接返回。如果题目改成“和可以被 K 整除的子数组数量”比如LeetCode 974思路就变成用前缀和对 K 取模作为哈希表的 key处理方法几乎一模一样。我个人认为560价值最大的地方在于它让人真正理解了哈希表在子数组问题里扮演的角色——它本质上是把“找前面的某个状态是否存在/出现多少次”这个查询从 O(n) 降到了 O(1)。这个思想在以后的很多题目里都会反复出现。3. LeetCode 239滑动窗口最大值单调队列是比堆更优的存在3.1 为什么固定的窗口大小反而更麻烦239的题目描述很直白给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧你只可以看到滑动窗口内的 k 个数字每次窗口向右移动一位返回滑动窗口中的最大值。第一直觉是每个窗口里用一次遍历找最大值这显然是 O(n*k) 级别的复杂度。稍微优化一点的想法是维护一个大顶堆堆顶就是当前窗口的最大值窗口滑动时往堆里加入新元素、移除离开窗口的元素。这个思路是正确的时间复杂度也能做到 O(n log k)但LeetCode的测试数据规模在 10^5 级别O(n log k) 能过只是不是最优解。这道题真正想让你掌握的解法是单调队列。它能把这题的时间复杂度压到 O(n)——严格地说每个元素最多入队一次、出队一次均摊下来每次操作都是 O(1)。很多初学者会困惑一个问题堆也支持快速取最大值为什么这题不用堆原因在于滑动窗口的窗口是有限制的堆里可能残留一些已经滑出窗口的元素而堆这种数据结构并不支持按值删除任意元素只能等它自己慢慢浮到堆顶才能被清理。这就导致堆顶那个最大值可能早就离开了窗口我们却依然把它当成合法候选值。每次要清理堆里的失效元素最坏情况下复杂度又退化了。单调队列的出现恰好同时解决了“快速取最大值”和“元素过期”这两个需求。3.2 单调队列的思想与维护过程为了直白一点我用一个例子来走一遍流程。假设 nums [1, 3, -1, -3, 5, 3, 6, 7]k 3队列里我存的是元素下标而不是元素值因为只有存下标才能判断元素是否已经滑出窗口。维护两条规则新元素入队之前把队列尾部所有比新元素小的元素全部弹出。这个操作保证了队列从头到尾的元素值是单调递减的队头永远是窗口内的最大值。队头元素如果已经不在当前窗口中把它从队头弹出。用例子走一遍。窗口从下标 0 开始扩张前 3 个元素按规则依次处理后队列里存的状态大致是 [1, 2]下标对应值 [3, -1] 或类似情况因为值 3 是最大的所以留在队头。窗口每次向右移动时先执行“移除下标超出窗口范围的队头”再加入新元素前做“弹出队尾更小值”然后队头就是当前窗口最大值。注意这里有个很容易被忽略的细节为什么队尾那些比新元素小的值可以放心地弹出因为在窗口内只要新元素存在那些比它小、又排在它前面的元素就永远不可能再成为最大值了。它们比新元素更早过期而且值还更小留着没有任何意义。这其实是一种非常典型的贪心思想用绝对劣势元素换取空间和时间的双赢。3.3 实现代码与复杂度详解下面我给出Java版本的标准写法class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] result new int[n - k 1]; // 双端队列存的是元素下标 DequeInteger deque new ArrayDeque(); for (int i 0; i n; i) { // 1. 移除队头滑出窗口的元素 if (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 2. 从队尾弹出所有比当前元素小的值 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } // 3. 当前元素下标入队 deque.offerLast(i); // 4. 窗口形成后每次把队头记录到结果中 if (i k - 1) { result[i - k 1] nums[deque.peekFirst()]; } } return result; } }几个需要说明的决策点为什么队尾弹出条件用而不是这里如果只用那么两个值相等的元素都会留在队列里。虽然不影响最终结果但队列会多存一些永远不会被选中为最大值的重复元素白白浪费空间和时间。用可以保证重复值中更靠右的那个留下左侧重复值被提前淘汰。实测在大量重复元素的数据集上的写法性能要好一些。为什么队头过期判断里用的是下标小于i - k 1因为窗口的左边界等于i - k 1如果队列中的下标小于这个值说明它已经滑出窗口左侧必须清理。双端队列选型上Java里ArrayDeque比LinkedList更适合这个场景因为ArrayDeque底层是循环数组实现均摊 O(1) 的访问速度更稳定也不涉及链表的节点对象开销。时间复杂度的严谨分析如下每个下标最多被加入队列一次、弹出队列一次所以全部循环中所有 while 循环的总执行次数是 O(n)加上主循环本身也是 O(n)整体 O(n) 没跑。空间复杂度是 O(k)队列里最多同时存在 k 个下标。3.4 变形题和工程上的联想单调队列在LeetCode里的变形非常多最经典的包括“滑动窗口中的最大值与最小值的差值”“满足条件的最短/最长子数组”之类。工程上如果你接触过流式计算和实时指标监控一定能反应过来——单调队列就是滑动窗口最小值/最大值滤波的一个很自然的实现模型。上面热词里就出现了“滑动窗口滤波”相关的词这类问题在嵌入式、信号处理、实时系统里都经常遇到。算法题刷到后面你会发现它跟工程实践并不是两条平行线。4. LeetCode 76最小覆盖子串双指针滑动窗口的完整收缩逻辑4.1 题目本质是找最短可行区间“最小覆盖子串”的题意是给一个字符串 s 和一个字符串 t返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在这样的子串则返回空字符串。这里的“涵盖”指的是字符种类和数量都要不少于 t 中对应字符的数量。这道题和前面两道最大的区别在于窗口的大小不固定而且目标是找“最短”。这种“要找满足某个约束条件的最短连续区间”的题目几乎都是双指针滑动窗口的射程范围。为什么因为满足条件具有单调性——窗口越大越容易满足条件窗口越小越难所以从“满足”到“不满足”这个状态变化是有方向的双指针可以放心地一伸一缩地去找边界。从暴力角度理解任何一个子串都可以由 left 和 right 两个边界确定双指针本质上就是在高效地枚举一组不重不漏的边界组合。关键是要设计好“什么时候扩张、什么时候收缩”的判断逻辑。4.2 需求字符计数的设计如何用两个计数器判断全覆盖一个直观的做法是用两个哈希表一个记录 t 中每个字符的需求量一个记录当前窗口中每个字符的拥有量。每个右指针移动到新字符时更新拥有量然后判断拥有量是否全部不少于需求量。如果全部满足说明存在一个可行窗口这时尝试收缩左指针。但这里有个性能敏感点如果每次都把所有字符种类遍历一遍去判断是否全覆盖哈希表最大可能有几十上百个键虽然也能过LeetCode的数据量但不是最优雅的写法。更好的方案是维护一个变量needCharCount或者叫matched表示当前窗口中“已经满足需求量”的字符种类数。具体逻辑是右指针扩张时如果当前字符在 t 中需要就把窗口里的计数加一。当这个字符从“不满足需求量”变成“满足需求量”时needCharCount加一。当needCharCount等于 t 中不同字符的总数时说明窗口已经完整覆盖了 t。左指针收缩时反向操作如果某个字符因为移出窗口导致从“满足需求量”变成“不满足需求量”needCharCount减一。这样我们就把“判断是否覆盖”从 O(|字符集|) 降到了 O(1)。在追求极限性能的代码里这个优化非常关键。4.3 完整实现和收缩时机的把握直接看Java代码在LeetCode评测里这版可以跑到 2ms 左右击败 95% 以上class Solution { public String minWindow(String s, String t) { if (s.length() t.length()) { return ; } // 记录 t 中每个字符的需求量 int[] need new int[128]; for (char c : t.toCharArray()) { need[c]; } int totalNeed 0; for (int count : need) { if (count 0) { totalNeed; } } int left 0; // 窗口左边界 int matched 0; // 当前已达标的字符种类数 int minLen Integer.MAX_VALUE; int minStart 0; char[] chars s.toCharArray(); int[] window new int[128]; for (int right 0; right chars.length; right) { char c chars[right]; // 扩张更新窗口计数 window[c]; // 如果当前字符的需求量已被满足matched增加 if (need[c] 0 window[c] need[c]) { matched; } // 当窗口完全覆盖 t 时尝试收缩左边界 while (matched totalNeed) { int currentLen right - left 1; if (currentLen minLen) { minLen currentLen; minStart left; } char leftChar chars[left]; // 收缩前先判断移除后是否会影响达标状态 if (need[leftChar] 0 window[leftChar] need[leftChar]) { matched--; } window[leftChar]--; left; } } return minLen Integer.MAX_VALUE ? : s.substring(minStart, minStart minLen); } }这段代码里最烧脑的一点就是那两条if判断的顺序问题。在收缩阶段为什么必须先判断window[leftChar] need[leftChar]再执行window[leftChar]--因为我们要判断的是“移除这个字符之前它在窗口里的数量是否刚好等于需求量”。如果刚好等于那移除之后就会变成“不满足”状态matched减一。如果之前窗口里的数量已经超过了需求量移除一个下来还满足需求那matched不发生变化。这个顺序如果写反了先减再判断判断的就变成“移除之后是否还等于需求量”整个逻辑就会彻底错乱。另外注意一点扩张阶段matched增加的判断条件是window[c] need[c]而不是或。因为matched只记录“从不满足到满足”这个状态变化的次数当字符数量已经超过需求量后再加字符不应该重复增加matched。4.4 为什么右指针不需要回退很多刚接触滑动窗口的读者会有一个根深蒂固的疑问收缩左边界之后右指针是不是也应该回退一下重新确认一下窗口内部的状态不需要。因为收缩后窗口依然满足覆盖条件——当然我们收缩的停止条件恰好在“不满足”的前一步。下一次循环继续右移右指针时只需要在这个“几乎覆盖”的窗口基础上继续累加即可不需要任何回退。每个字符被 left 经过一次、被 right 经过一次整体的复杂度就是两个指针移动距离之和 O(n)。这个“不回退”的特质正是滑动窗口类算法能高效工作的核心保证。理解这点以后76题基本就没有盲区了。5. 三道题放在同一张表里对比以及实战刷题顺序建议5.1 核心信息对照表直接上一张整理好的对比表方便复习的时候快速回忆对比维度LeetCode 560LeetCode 239LeetCode 76题目目标和为 K 的子数组数量每个滑动窗口的最大值覆盖 t 的最短子串核心数据结构哈希表 前缀和单调双端队列双指针 计数数组窗口大小不固定固定为 k不固定动态伸缩数组是否有负数有无所谓不适用字符串关键前提前缀和可以做差求区间和单调性决定淘汰规则覆盖状态单调变化时间复杂度O(n)O(n)均摊O(n)最容易踩的坑先更新再查询导致重复计数队头过期清理不及时收缩左边界时机和 matched 的维护顺序这个表对我来说才是整套专题复习的浓缩精华。每次刷到类似题型先想想这题目更靠近表里哪一列基本就能决定解题方向。5.2 建议的刷题顺序和配套练习个人经验是不要按题号顺序刷而是按“解法血缘”去刷。第一轮先把560做透然后立刻做974和可被 K 整除的子数组、525连续数组、523连续子数组和这些题共用同一套前缀和思维。第二轮做239接着做LeetCode 滑动窗口最大值相关的衍生题比如剑指Offer 59-I题型几乎一样可以白嫖一遍熟悉的流程。第三轮做76做完以后再做LeetCode 3、424、1004这几道都是同一种双指针收缩逻辑在不同约束条件上的翻版。5.3 实战中额外总结的几点心得最后分享几个只有真正提交过很多次才会注意到的细节都是我从“超时”和“答案错误”的惨痛经历里总结出来的第一560这类前缀和题目哈希表的初始值put(0, 1)千万别省。少了这一行所有从头开始的子数组全部会漏算。我见过太多人在这个初始条件上卡了好几个小时。第二239的单调队列里存的是下标不是值这个设计不是风格问题而是必要设计。不存下标你根本没法判断队头元素是不是已经过期存值配合值的比较只能做出一个“局部最大值”而不是真正的窗口最大值。第三76题的matched totalNeed这个判断条件在窗口非常长、字符种类非常多时特别容易出bug。如果你发现答案中多算了或者少算了某些子串先去检查matched的维护是否只在状态变化的那一次更新而不是每次都无条件更新。第四不管哪道滑动窗口题只要你用数组或ArrayDeque替代哈希表和链表在LeetCode上时间基本都能快上一大截。这不是玄学而是因为 LeetCode 的测试用例里大量重复字符和超大测试规模哈希冲突和链表节点分配的开销会被无限放大。能用固定数组int[128]或int[26]的场景绝对不比 HashMap 差。三题刷透以后你对子数组问题的理解会明显不一样。之后再遇到什么“最长无重复子串”“最大连续1的个数”“至少有K个重复字符的最长子串”这类题你会发现它们其实都在同一个坐标系里只是有的变了约束有的换了数据结构内核始终是那老三样前缀和、单调队列、双指针。