企业官网建设流程全解析

先交代一下背景。我去年集中刷力扣的时候，把 hot 100 按题型拆开过一遍，其中最让我觉得“明明代码不长、但就是容易绕晕”的，就是子串篇。网上讲这三道题的文章不少，但有的一上来就丢代码，有的把原理写得比题还难懂。这篇我换个讲法，把每一道题背后的思考逻辑、代码为什么这么写、哪些地方容易踩坑，全部展开讲清楚。目标是让一个刚刷到中等题的人，也能顺着思路把代码自己写出来，而不是背答案。

先说清楚：力扣 hot 100 里真正归类到“子串篇”的核心题，通常指的是这三道——和为 K 的子数组（560）、滑动窗口最大值（239）、最小覆盖子串（76）。它们分别代表了子串问题的三种典型解法：前缀和 + 哈希表、单调队列、双指针滑动窗口。这三道题各管一个方向，彼此不重叠，把它们搞明白，后面碰到一堆长的很像的题，就能直接归类到这三个流派里。

1. 子串篇到底在考什么：先建一张全景地图

1.1 子串和子序列是两码事

很多人在刷题初期会混淆一个概念：子串（substring）和子序列（subsequence）不是一回事。子串要求元素在原数组或原字符串里必须连续，比如"abc"的子串有"a"、"ab"、"abc"等，但"ac"不是子串，因为中间隔了一个b。子序列只要求相对顺序不变，不要求连续，所以"ac"是"abc"的子序列。

这个概念为什么重要？因为“连续”这个约束，决定了你能用滑动窗口这一类线性扫描的方法。如果题目改成子序列，那基本就要往动态规划的方向想了。hot 100 里的子串篇三道题，全部建立在“连续”这个前提下，这意味着你可以在一次遍历里，通过维护窗口的起止位置来覆盖所有可能的情况。

1.2 子串篇的三道题，恰好对应三种解法流派

这三道题放在一起并不是随机的，它们覆盖了子串问题最主流的三种解法思路：

• 和为 K 的子数组（560）教你怎么处理“需要快速计算任意一段连续区间的某种属性”的问题，答案是用前缀和预处理，再用哈希表加速查找。
• 滑动窗口最大值（239）教你怎么在窗口持续滑动的过程中，高效维护窗口内的最值，这需要设计一种能在头部弹出过期元素、在尾部插入新元素的特殊数据结构——单调队列。
• 最小覆盖子串（76）教你怎么用两个指针维护一个动态窗口，在满足约束条件的前提下寻找最优窗口。这是双指针滑动窗口最经典的范式，后面大量字符串题都是套这个模板。

换句话说，这三道题就像一个工具箱里的三把扳手，型号不一样，用法也不同。你把这三个工具分别玩熟，子串这类问题的大框架就立起来了。

1.3 本文的刷题路线图

建议按题目顺序刷，不要跳跃。先刷 560，因为它只需要一种数据结构（哈希表），思路最独立；再刷 239，因为它需要你稍微动点脑筋设计单调队列，但没有复杂的窗口收缩逻辑；最后刷 76，因为它的双指针框架里多了“计数”“收缩”这些状态管理，是在前两题基础之上的综合应用。

下面我按这个顺序，一道题一道题拆。

2. 和为 K 的子数组（560）：前缀和为什么能救你

2.1 暴力的困境：为什么 O(n²) 过不了

题目很简单：给定一个整数数组nums和一个整数k，要求统计连续子数组中和为k的个数。

最直觉的做法是枚举每个子数组的起点和终点，累加求和，判断是否等于k。伪代码大概是这样：

int count = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { int sum = 0; for (int p = i; p <= j; p++) sum += nums[p]; if (sum == k) count++; } }

这个是 O(n³)，显然不行。优化的第一步很自然：既然每次都重新累加太浪费，那我可以边扩右边界边累加，于是变成两层循环 O(n²)。力扣给的数组长度动辄10^4量级，O(n²) 就是10^8次操作，在 Java 里大概率超时，Python 更不用说。所以必须换思路。

2.2 前缀和 + 哈希表的完整推导过程

核心转换在于一个数学事实：连续子数组的和，可以表示为两个前缀和之差。

定义pre[i]为数组前i个元素的和（即nums[0]到nums[i-1]的和）。那么从下标j到下标i（在 Java 里左闭右开更常见）的子数组和就是：

pre[i] - pre[j] = nums[j] + nums[j+1] + ... + nums[i-1]

如果这个值等于k，就说明pre[j] = pre[i] - k。

这句话是整个题目的题眼。它把“寻找和为 k 的子数组”这个二维搜索问题，转换成了“当前前缀和减去 k 之后，是否在之前出现过”的一维查找问题。

所以流程变成这样：从左往右遍历数组，同时维护当前前缀和presum。每到一个位置，先看presum - k是不是已经在哈希表里出现过了，如果出现过，它出现的次数就是“以当前位置结尾、和为 k 的子数组”的个数。然后把当前的presum也记进哈希表，继续往后走。

这里有一个容易被忽略的细节：为什么哈希表里存的是“次数”而不是“是否存在”？因为同一个前缀和完全可能在多个位置出现，比如数组[1, -1, 0]，前缀和在某个值上会出现多次，每一次都对应一个不同的起点，所以必须累计次数。

还有一个关键初始化：必须先把pre[0] = 0放入哈希表，次数为 1。为什么要这样？举个例子，如果nums = [3, 4, 7]，k = 7，遍历到第 3 个位置时presum = 14，要找14 - 7 = 7。而前缀和 7 恰好来自nums[0] + nums[1]，也就是pre[2]。但如果你想找的子数组从下标 0 就开始了，比如nums[0] + nums[1] + nums[2] = 14，此时要找pre[3] - k = 7，这个 7 并不在之前的前缀和里——除非我们人为定义pre[0] = 0出现过。初始化 0，就是为了覆盖“从数组开头到当前位置的整个区间”这种情况。

2.3 Java 实现与两个隐藏的坑

代码非常短，但短代码里埋着两个很关键的坑。

public int subarraySum(int[] nums, int k) { // key: 前缀和的值， value: 该前缀和出现的次数 Map<Integer, Integer> preSumCount = new HashMap<>(); // 初始化：前缀和为0的“空数组”算出现过一次 preSumCount.put(0, 1); int preSum = 0; int count = 0; for (int num : nums) { preSum += num; // 核心：如果之前存在 preSum - k，说明有若干子数组的和等于k if (preSumCount.containsKey(preSum - k)) { count += preSumCount.get(preSum - k); } // 把当前前缀和统计进去 preSumCount.put(preSum, preSumCount.getOrDefault(preSum, 0) + 1); } return count; }

第一个坑：顺序问题。一定是“先查后存”，不能反过来。如果先把当前的preSum存进哈希表，再去查preSum - k，当k = 0的时候，你会把当前位置自己匹配进去，导致重复计数。比如nums = [1, -1]，k = 0，遍历时一个合法的子数组都没有。但如果先存再查，第一个位置preSum = 1存进去，查1 - 0 = 1能查到，就会错误地算出一个子数组。这个错误非常隐蔽，运行小的测试样例时甚至可能碰巧对，只有k = 0时立刻暴露。

第二个坑：preSum理论上可能会超过int范围吗？这题给的约束里，数组元素绝对值较小，preSum用int一般没问题。但如果你在扩展题（比如矩阵区域和）里遇到类似逻辑，建议直接用long，省得边界数据一上来就溢出，排查起来非常痛苦。工程习惯上，涉及累加求和且数据量不确定的场景，优先long。

3. 滑动窗口最大值（239）：单调队列是怎么炼成的

3.1 为什么不要用优先队列

题目：给定数组nums和窗口大小k，窗口从左往右滑动，每次移动一个位置，要求输出每个窗口内的最大值。

看到“最大值”，很多人第一反应是维护一个大顶堆（优先队列）。思路似乎很顺：每次窗口进入一个新元素，就把这个元素加入堆里，输出堆顶，然后移动窗口时把离开窗口的元素删掉。但这里有两个问题。

第一，Java 的PriorityQueue删除任意元素是 O(n) 的，不是 O(log n)，因为它是通过线性扫描找到元素再删除的。所以整个算法退化成了 O(n·k)，和暴力没本质区别。第二，堆里并不是只有当前窗口的元素，怎么判断堆顶到底是不是当前窗口的？你还得额外记录下标，然后循环弹出“下标已经滑出窗口”的堆顶元素。这一步本身没错，但如果你用的是堆，每次删除窗口内的任意元素都会拖慢速度。

所以，如果要追求 O(n) 的解法，必须有比堆更聪明的数据结构。答案就是单调队列——准确说，是一个双端队列（Deque），它维护的元素始终保持单调递减。

3.2 单调队列的核心设计：为什么必须存下标

单调队列的核心思想可以这样理解：在队列内部，我们永远只保留“可能成为窗口最大值”的候选元素，那些永远不可能成为最大值的元素，趁早丢掉。

怎么判断一个元素“永远不可能成为最大值”？看两个条件：一是它已经在窗口外面了（下标太小），二是它比某个更靠右、更新的元素小。第二种情况尤其重要：假设队列里尾部有一个值5，现在新来的元素是7，那么在之后的所有滑动过程中，只要窗口里有7，5就永远不可能被输出为最大值。就算7将来被滑出窗口，5可能比7更早被滑出，所以在7存在期间，5就是纯粹的累赘。因此，每次新元素入队前，把队尾所有小于或等于新元素的值全部弹出，只保留严格递减的序列。

为什么存下标而不是存值？这是实现时要特别注意的：滑窗是一个不断“移动”的过程，窗口左边界在变，你必须知道每个元素什么时候过期。如果只存值，你根本不知道这个值对应数组里的哪个位置，也就无法判断它是否已经滑出窗口。所以队列里存的一定是下标，取值的时候再去nums[deque.peekFirst()]取。

3.3 完整代码与每一行的意图

public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; // 一共会产生 n-k+1 个窗口 int[] res = new int[n - k + 1]; // 双端队列，维护数组下标 Deque<Integer> deque = new ArrayDeque<>(); int idx = 0; for (int i = 0; i < n; i++) { // 1. 清理队头过期元素：窗口左边界是 i-k+1 while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) { deque.pollFirst(); } // 2. 维护单调递减：当前元素比队尾元素大，队尾元素永远不会成为最大值 while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) { deque.pollLast(); } // 3. 当前元素入队 deque.addLast(i); // 4. 窗口完整（右边界达到 k-1）后，才开始记录结果 if (i >= k - 1) { res[idx++] = nums[deque.peekFirst()]; } } return res; }

这里面有几个值得单独说明的点。

第 1 步为什么用while？表面上看，每次窗口只滑动一格，最多只有一个元素过期，用if就够了。但在实际运行中，由于第 2 步可能弹出大量队尾元素，队头其实是动态变化的，用while可以保证逻辑的完备性。虽然这题里if也能过，但我建议统一用while，因为后续很多变体题（比如滑动窗口中位数）里，过期元素可能不止一个。

第 2 步用<=而不是<，是个细节优化。如果新元素和队尾元素相等，保留旧的还是新的？其实都一样，因为它们的值相等。但如果你用<，队列里就会同时存在两个相等值的下标，白白占空间，还需要额外的弹出操作。用<=直接把旧元素淘汰掉，队列更精简，输出结果完全不受影响。

复杂度方面：每个元素最多入队一次、出队一次，所以整体是 O(n)。空间上，队列最多存k个下标，是 O(k)。

4. 最小覆盖子串（76）：双指针滑动窗口的经典范式

4.1 从“可行解”到“最优解”：两阶段收缩法

题目：给你字符串s和t，在s中找到包含t所有字符的最小子串。注意t里的字符可能有重复，比如t = "AABC"，那么窗口里至少要有两个A、一个B、一个C才算覆盖。

很多人第一次看到这题会卡在“怎么判断当前窗口是否覆盖了t”上。如果你每次都用临时哈希表去逐个比对，复杂度就爆了。正确做法是引入一个整数变量valid，用它记录“当前窗口里，已经满足数量要求的字符种类数”。当valid == need.size()时，说明t里所有字符都已经被覆盖，当前窗口是一个可行解。

有了可行解之后，求“最小覆盖”的思路就是标准的双指针：

• 右指针不断右移，扩大窗口，直到窗口满足覆盖条件；
• 一旦覆盖，尝试左指针右移，收缩窗口，看能不能在仍然覆盖的情况下让窗口更短；
• 每次收缩前记录当前窗口的长度和起始位置，更新最优解；
• 当收缩到不再覆盖时，暂停左指针，继续右移右指针找下一个可行解。

这个过程像一个尺蠖在字符串上爬行：右端探路、左端收缩，全程只遍历两遍，复杂度 O(n)。

4.2 用 valid 变量避免无谓的哈希表比较

具体实现上，我维护两张表：一张记录t里每个字符的需求量need，一张记录当前窗口内各字符的数量window。右指针每次读入一个字符c时，如果c是t中需要的字符，就把window[c]加一。加完之后，如果window[c]恰好等于need[c]，说明这个字符的数量已经满足要求，valid加一。

什么时候缩小窗口？valid == need.size()的时候。注意need.size()指的是字符种类数，而不是t的长度。比如t = "AABC"，need里有A、B、C三种字符，size 是 3。valid达到 3 就说明窗口里的A至少有 2 个、B至少有 1 个、C至少有 1 个，即窗口覆盖了t。用字段数来比较，就避免了每次都要遍历整张哈希表去判断是否覆盖。

左指针收缩时同样要维护valid和window。如果左指针指向的字符d也是need关心的字符，那么窗口去掉一个d之后，如果window[d]已经比need[d]少了，说明这个字符从“满足”跌到了“不满足”，valid要减一。然后window[d]减一。

4.3 代码实现与隐藏的坑

public String minWindow(String s, String t) { // 记录 t 中每个字符的需求量 Map<Character, Integer> need = new HashMap<>(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c, 0) + 1); } // 记录当前窗口中每个字符的数量 Map<Character, Integer> window = new HashMap<>(); int left = 0, right = 0; int valid = 0; int start = 0; int minLen = Integer.MAX_VALUE; while (right < s.length()) { char c = s.charAt(right); right++; if (need.containsKey(c)) { window.put(c, window.getOrDefault(c, 0) + 1); if (window.get(c).equals(need.get(c))) { valid++; } } // 窗口已覆盖 t，开始收缩 while (valid == need.size()) { // 尝试更新最小覆盖子串 if (right - left < minLen) { minLen = right - left; start = left; } char d = s.charAt(left); left++; if (need.containsKey(d)) { if (window.get(d).equals(need.get(d))) { valid--; } window.put(d, window.get(d) - 1); } } } return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen); }

写这段代码时，我踩过两个特别值得说的坑。

第一个坑：Integer的比较。window.get(c)和need.get(c)返回的都是Integer对象，如果你直接写==，在值超过 127 时（Java 的Integer缓存上限），两个相同数值的Integer对象比较结果可能是false。这会导致valid永远加不到need.size()，程序直接死循环或返回空串。所以这里必须用.equals()比较。

第二个坑：收缩时valid和window的更新顺序。如果window[d]等于need[d]，说明减少这个字符会让它从“满足”变为“不满足”，所以要先把valid减一，再把window[d]减一。反过来也行，但你必须保证“判断是否等于”时用的是减之前的值。很多文章这部分的代码写得含糊，我建议你在本地多跑几个例子，把valid的变化打印出来看，会对这个状态理解得特别透。

5. 从子串篇延伸到更多题目：一道题裂变成一类题

5.1 这三道题的变体到底长什么样

学完三道核心题，你会发现自己仿佛拿到了三套模板，很多 hot 100 之外的题其实都是它们的变体。我整理了一张对照表，刷题时可以按这个分类去套思路。

这张表的价值在于：刷题时不要只背题，要识别“它到底是哪个模板的变形”。我自己的习惯是，每刷完一道新题，先问自己一句：这道题和 560、239、76 里哪一道最像？如果像 76，那大概率是双指针；如果像 239，大概率要上单调队列；如果问的是“某个区间和等于多少”，那优先想前缀和。

5.2 无重复字符的最长子串是最轻松的练手题

这里我想单独说下第 3 题，因为它和 76 太像了，但简单得多，特别适合验证自己是否真的掌握了双指针模板。

第 3 题要求在字符串里找最长的不含重复字符的子串。用左右指针维护窗口，右指针每次扩进一个新字符，同时更新这个字符在窗口里的计数。如果发现某个字符计数大于 1，说明窗口内有重复，那就收缩左指针，直到这个字符计数回到 1。每次右指针扩张后记录窗口长度，更新最大值。

和 76 对比，你会发现它俩骨架完全一样：右指针探路、维护计数、左指针收缩。不同之处只是第 3 题的收缩条件是“出现重复字符”，76 的收缩条件是“窗口已经覆盖 t”。所以如果你 76 理解得费劲，可以先从第 3 题开始写一遍，再回来写 76，会顺很多。

5.3 有人说接雨水也该归到子串篇？

这个观点我偶尔能刷到，有些人在分类里会质疑：为什么接雨水（42）不在子串篇里？

说白了，接雨水属于“技巧”类，它用的是双指针（或单调栈），但它的双指针思路是为了按列计算水量，而不是维护一个覆盖某个约束的滑动窗口。它和 76 虽然都用了双指针，但一个是“约束满足型”的双指针，一个是“几何计算型”的双指针，思维方式差异很大，所以力扣没有把它放进子串篇。我建议不要纠结分类，而是要抓住一个本质：双指针有几种典型用法，滑动窗口只是其中一种，接雨水是另一种。

另外，如果你的目标是 hard 题里刷子串，那 395（至少有 K 个重复字符的最长子串）是个很好的进阶目标。它表面是滑动窗口，实际因为“哪些字符可以出现在子串里”是不确定的，所以经典的滑动窗口并不能直接套。需要枚举窗口中包含的字符种类数，比如限制窗口里最多出现h种不同字符，然后对每个h跑一次双指针。这里面有个隐藏的高频考点：当一个问题无法直接滑动窗口时，考虑给窗口增加一个限制条件，把问题拆成多个子问题进行求解。

我个人的刷题建议是：先把这三道子串核心题做到闭着眼睛能默写，再尝试把它们各自最常见的变体做一遍，最后去挑战 395。按这个路径走，子串这个分类基本就稳了。我自己刷完这一轮之后，最大的体会是——很多题考察的并不是你临时想出新算法的能力，而是你脑海里有没有把问题归类到已知模板的敏感度，这种敏感度只有靠反复对照总结才能建立起来。