企业官网建设流程全解析

面试过的人多半有过这种体验：算法题刷了不少，但一到“子数组”“区间”这类问题，脑子里能想起来的方法就只剩暴力枚举了。稍微好一点的知道该用双指针，但拆开LeetCode 560、239、76这三道题就会发现，它们虽然都长着一副“子数组题”的脸，真正的考点却完全不在一个维度上——560的核心是前缀和与哈希表的组合，239考的是滑动窗口与单调队列的配合，76则是双指针窗口收缩的经典模板。这三道题放在一起刷，其实就是把“子数组问题”这条线的最底层逻辑给串起来了。

这篇文章不打算泛泛地讲概念，而是把这三道题从头到尾拆开揉碎。你能看到每道题的暴力解是怎么一步步演化的、优化到底优化掉了什么、边界条件为什么会卡人、以及一些只有在实际提交时才会遇到的坑。不论是刚开始刷LeetCode、还是已经刷了百来题想整理思路，这份笔记应该都能帮上忙。

1. 这道专题到底在考什么：先建立一个总体的解题坐标系

1.1 滑动窗口不是银弹，它有自己的边界条件

很多人一看到“连续子数组”就想上滑动窗口，这个直觉对了一半。滑动窗口本质上是双指针的一个特化应用，它成立的先决条件是：窗口的扩张和收缩之间存在单调性。也就是说，右指针右移时窗口的某个属性单调变化，左指针右移时这个属性反向单调变化，只有在这种情况下，双指针来回移动才不会有漏解的问题。

拿LeetCode 239来说，我们要求的是每个滑动窗口内的最大值，这里窗口大小是固定的，右指针和左指针都在单向向前移动，这满足滑动窗口的物理结构。但问题在于，我们要求“最大值”这件事，但它随着窗口的收缩并不具备单调性——窗口变小，最大值是可能变大也可能变小的，这就没办法直接用普通的双指针维护窗口内某个值的信息。于是239引出了单调队列这个数据结构。

相比之下，LeetCode 76的“最小覆盖子串”就非常典型地满足了单调性：当右指针扩张时，窗口内覆盖目标字符的进度只增不减；当左指针收缩时，进度只减不增。所以它是一个标准的双指针滑动窗口模板题。

而LeetCode 560就更特殊了，它虽然叫“和为K的子数组”，但数组中又有正数又有负数，窗口的“和”属性既不随扩张单调递增，也不随收缩单调递减。这种时候滑动窗口的指针移动策略直接失效，必须换成前缀和加哈希表的思路。

1.2 子数组问题常见的解法栈

把上面说的整理一下，子数组类问题其实有一条相对清晰的解法栈，做题的时候可以按这个顺序去试：

1. 如果没有单调性，暴力枚举所有子数组是保底方案，一般会超时但能帮你验证思路。
2. 如果窗口扩张/收缩时属性单调变化，优先考虑双指针滑动窗口。
3. 如果数组里有负数、要求的是某种累加值恰好等于目标，前缀和（通常配合哈希表）是通用解法。
4. 如果窗口内需要快速获得最大值/最小值，堆和单调队列是两个主力数据结构，通常更偏向单调队列。

这个坐标系建立起来以后，再去看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[j+1] - 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: 出现次数 Map<Integer, 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; } }

这个代码里有几个边界点值得展开说一下：

1. 为什么初始化时要放一个(0, 1)？因为前缀和数组里本来就包含prefix[0] = 0，表示一个元素都没有的“空前缀”。这样假设的好处是，当某个位置的前缀和恰好等于 k 时，prefixSum - k = 0，能直接匹配到这个初始记录，把“从头开始到当前位置”的整个子数组算进去。
2. 数组中有负数和零时，前缀和不一定是单调递增的，同一个前缀和值可能反复出现多次，所以哈希表里要记录的是“出现次数”而不是“是否出现过”。这是这道题和“两数之和”写法上最大的区别。
3. 答案的计数范围可能很大，题目里没有说明模数，所以用 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]; // 双端队列，存的是元素下标 Deque<Integer> 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 核心信息对照表

直接上一张整理好的对比表，方便复习的时候快速回忆：

这个表对我来说才是整套专题复习的浓缩精华。每次刷到类似题型，先想想这题目更靠近表里哪一列，基本就能决定解题方向。

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个重复字符的最长子串”这类题，你会发现它们其实都在同一个坐标系里，只是有的变了约束，有的换了数据结构，内核始终是那老三样：前缀和、单调队列、双指针。