企业官网建设流程全解析

1. 题目拆解：先搞清楚“和为 K 的子数组”到底在问什么

1.1 题目到底在说什么

力扣 560 题“和为 K 的子数组”，题目描述很简短：给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的子数组的个数。

这里有个关键点很多人第一次读题会忽略：题目说的是子数组，不是子序列。子数组意味着必须是连续的一段，顺序不能乱，也不能跳着选。比如nums = [1, 2, 3]，那么[1, 3]不算子数组，因为 1 和 3 在原数组中不相邻；[2, 3]才是合法的子数组。

我举个具体的例子，题目给定的示例是：

输入：nums = [1, 1, 1], k = 2 输出：2

这个数组里，和为 2 的连续子数组分别是[1, 1]（下标 0 到 1）和[1, 1]（下标 1 到 2），所以答案是 2。注意这两个子数组的元素值相同，但下标范围不同，算作两个不同的结果。

再看一个稍微复杂点的例子：

输入：nums = [1, 2, 3], k = 3 输出：2

这里的两个答案分别是[1, 2]（下标 0 到 1）和[3]（下标 2 到 2）。注意单个元素也可以作为子数组，这个点在做边界判断时容易漏掉。

还有一点值得提醒：nums里的元素可以是负数。这会直接影响解法选择，我后面会专门展开。很多人第一反应是“连续子数组求和，那不就是滑动窗口吗”，但正因为数组里有负数，滑动窗口的双指针收缩策略会失效。这个坑，我当年第一次做的时候也踩过。

1.2 暴力解法的瓶颈所在

最直观的解法就是枚举所有可能的子数组区间。假设数组长度为n，任意一个子数组由左端点i和右端点j决定，其中0 <= i <= j < n。我只需要两重循环确定端点，再计算这个区间的和，和k相等就把计数加一。

这里有三种计算区间和的方式，它们的效率差别很大：

第一种是最朴素的：每次枚举i和j之后，再用一层循环从i加到j。这样是三层循环，时间复杂度是O(n³)，在力扣上连示例都要跑半天，完全不可取。

第二种是稍微优化一点：固定左端点i，然后让右端点j从i开始往右扩展，一边扩展一边累加，这样sum(i, j)就可以利用上一次的sum(i, j - 1)结果。代码写起来大概是：

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

这样降到了O(n²)，思路非常直白，没有任何技巧。但问题也很明显：当n到10^5量级时，n²就是10^10次运算，在力扣的评测环境下基本会超时。

第三种就是用前缀和数组预处理，把任意区间和的计算变成O(1)，但枚举区间仍然是O(n²)，总复杂度还是O(n²)。前缀和的思路本身非常有价值，它也是哈希表优化方案的基石，所以我把它放在下一节单独讲。

1.3 为什么不能用滑动窗口/双指针

我见过不少人在评论区问：“这题不是用滑动窗口就能做吗？”如果你也这么想，请先停下来想一个问题：滑动窗口的可行性前提是什么？

滑动窗口最经典的适用场景是数组元素全为正数。比如力扣 209 题“长度最小的子数组”，nums 全是正整数，窗口向右扩张时和会单调递增，所以当窗口内的和已经超过目标值时，左指针右移缩小窗口，窗口和一定减小，这种单调性保证了双指针的正确性。

但本题的nums允许负数。一旦有负数，窗口向右扩张时和可能会变小，左指针右移时和也可能会变大。单调性被打破，双指针就失效了。举个例子，nums = [1, -1, 0], k = 0，如果尝试用滑动窗口，你会发现很难决定什么时候收缩窗口。

这也解释了为什么这题的正确解法需要换个角度：我们需要一种不依赖数组元素正负性的统计方法，前缀和加哈希表就是为此设计的。

2. 前缀和：把“区间求和”变成“两个数的差”

2.1 前缀和数组的定义与推导

前缀和的定义很简单：定义prefix[i]表示数组nums从下标0到下标i的所有元素之和。为了处理方便，通常会额外增加一个prefix[0] = 0，表示空数组的前缀和。

于是：

prefix[0] = 0 prefix[1] = nums[0] prefix[2] = nums[0] + nums[1] ... prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

注意我这里用的是prefix[i]表示前 i 个元素的和，也就是说prefix数组的长度是n + 1而不是n。这样做的好处是：子数组nums[i..j]的和可以直接写成

sum(i, j) = prefix[j + 1] - prefix[i]

为什么是j + 1？因为prefix[j + 1]包含的是nums[0]到nums[j]这j + 1个元素的和，减去prefix[i]包含的nums[0]到nums[i - 1]这i个元素的和，剩下的正好是nums[i]到nums[j]。

你可以把前缀和理解成一组“里程碑”：要算任意两个里程碑之间的距离，只需要把两个里程碑的数值相减就行，不需要回头一步一步重新走一遍。这就是前缀和能加速的核心原理。

2.2 前缀和暴力枚举的改进效果

如果只使用前缀和数组，不配合哈希表，代码可以这样写：

int subarraySum(vector<int>& nums, int k) { int n = nums.size(); vector<int> prefix(n + 1, 0); for (int i = 0; i < n; i++) { prefix[i + 1] = prefix[i] + nums[i]; } int count = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (prefix[j + 1] - prefix[i] == k) { count++; } } } return count; }

相比最原始的O(n³)，这个版本已经快了不少，但仍然是O(n²)，没法通过大数据量的测试用例。真正的质变来自下一步：能不能不枚举所有区间，而是用一个哈希表把历史信息存下来，做到只遍历一次数组就得出答案？

2.3 前缀和数组的边界设计

在进入哈希表方案之前，我提醒一下边界设计。上面我采用的是prefix[0] = 0，prefix[i]表示前i个元素的和。网上也有代码写成prefix[0] = nums[0]，prefix[i]表示nums[0..i]的和。两种写法本质等价，但我在写代码时更推荐“前 i 个元素”这种，原因有二：

• 空数组的前缀和是 0，这样prefix[0]可以天然参与运算，不需要额外讨论i = 0的边界情况。
• 子数组区间的公式sum(i, j) = prefix[j + 1] - prefix[i]非常统一，左右端点不需要加一减一，出错率更低。

3. 哈希表优化：把 O(n²) 压到 O(n) 的关键

3.1 等式的变形是突破口

暴力求解的核心问题是：我需要枚举所有(i, j)组合，然后判断sum(i, j) == k。如果用前缀和表示，这个条件变成：

prefix[j + 1] - prefix[i] == k

把这个式子移项，就得到了一个非常关键的变形：

prefix[i] == prefix[j + 1] - k

这个式子是什么意思？它的意思是：当我在枚举右端点j的时候，我真正关心的是——在当前位置之前，有多少个前缀和的值等于prefix[j + 1] - k。有多少个这样的前缀和，就说明有多少个左端点i能使得nums[i..j]的和等于k。

于是，我不需要再枚举左端点，只需要在遍历数组的过程中，用一个哈希表记录每个前缀和出现的次数。每计算出一个新的前缀和current，我就去哈希表里查current - k出现了多少次，把次数累加到结果里。然后把这个current的次数加一，继续往后走。

一句话总结这个思路：我在每个位置只关心“从我之前某个位置到我当前位置，有没有和为 k 的子数组”，而哈希表告诉我答案。

3.2 核心代码实现（C++ / Python）

先看 C++ 版本：

class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> prefixCount; prefixCount[0] = 1; // 空前缀，和为 0，出现 1 次 int sum = 0; int count = 0; for (int num : nums) { sum += num; // 查一下有多少个前缀和等于 sum - k if (prefixCount.count(sum - k)) { count += prefixCount[sum - k]; } // 当前前缀和存入哈希表 prefixCount[sum]++; } return count; } };

再看 Python 版本：

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: prefix_count = {0: 1} total = 0 count = 0 for num in nums: total += num count += prefix_count.get(total - k, 0) prefix_count[total] = prefix_count.get(total, 0) + 1 return count

整个算法的时间复杂度是O(n)，空间复杂度也是O(n)，因为哈希表最多存n + 1个不同的前缀和。

代码看起来很短，但短代码往往藏了很多细节。下面我把几个关键点掰开揉碎讲清楚。

3.3 为什么初始化 m[0] = 1

这是新手最容易卡住的一行。很多人会问：“我还没开始遍历数组呢，为什么哈希表里要先放一个 0 进去？”

原因很简单：前缀和为 0 的情况在最开始时已经出现了一次，那就是“空数组”。空数组的和是 0，这是一个合法的“历史前缀”。

举个例子，nums = [3], k = 3。遍历到第一个元素 3 时，sum = 3，我需要查sum - k = 3 - 3 = 0出现在哈希表中的次数。如果不在哈希表里预先放{0: 1}，这里查到的是 0，那么答案就漏掉了[3]这个子数组。

换句话说，这个{0: 1}代表的是“下标 -1 之前的位置”，即从不包括任何元素时的状态。每个合法子数组的和都是从它左端点之前的前缀和到这个位置的前缀和之差，所以左端点之前可能什么都没有，对应的前缀和就是 0。

3.4 先查表还是先更新？顺序为什么不能乱

代码里的顺序是：

1. 累加sum
2. 查哈希表，累加结果
3. 把sum插入哈希表

这个顺序为什么不能颠倒？因为我要统计的子数组长度至少是 1。如果我先把当前sum插入哈希表，然后查sum - k，当k = 0时会发生什么？

// 错误的顺序 sum += num; prefixCount[sum]++; // 先插入 count += prefixCount[sum - k]; // 再查询

当k = 0时，sum - k == sum，先插入再查询，结果就是sum出现的次数包含了刚插入的这一次，也就是把长度为 0 的空子数组也统计进去了。题目要求的是子数组，长度不能为 0，所以这个多余统计必须避免。

正确的顺序是先查旧数据，再插入新数据，保证当前累积的前缀和不会影响同一轮查询。

我再说一个进阶理解：这一行顺序其实还决定了我们统计的“左端点”必须是“右端点之前的某个位置”，不能等于右端点本身。因为子数组的长度至少为 1，左端点最多到j（此时子数组只有一个元素nums[j]），但左端点之前的那个“前缀端点”最多到j - 1，所以当前这个前缀和不能作为自己的左端点前缀。

4. 常见错误与排查细节

4.1 int 溢出

prefix[i]的累加可能会超出int的范围。比如数组长度是10^5，每个元素值可以达到10^4，那么前缀和最大可以达到10^9，这个还在int范围内。但如果题目把数值范围调大，或者某些变态用例叠加，int很容易溢出。

我在写 C++ 代码时习惯把sum和哈希表的 key 类型直接定义成long long或long，避免在边界用例上翻车。虽然力扣这道题的原始数据范围用int也问题不大，但这是一个好的防御性编程习惯。

unordered_map<long long, int> prefixCount; long long sum = 0;

这样即使nums[i]是很大的整数，也不会发生未定义行为。

4.2 负数与零值造成的问题

前缀和允许负数，也允许重复出现。比如nums = [1, -1, 0, 0]，这个数组的前缀和依次是1, 0, 0, 0，其中 0 出现了多次。

哈希表的 value 存的是“次数”而不是“位置”，这很关键。为什么要存次数？因为同一个前缀和可能对应多个不同的左端点，每一个都代表一个合法的子数组起点。比如prefix sum = 0出现了三次，就意味着存在三个不同的起点能形成和为目标值的子数组。

负数还会导致另一个问题：前缀和不单调，所以不能在前缀和数组上做二分查找，也不能用双指针。你必须依赖哈希表这种支持随机查询的结构。

4.3 对 map 与 unordered_map 的选择

C++ 里map和unordered_map都能存键值对，但底层实现不同：

• map基于红黑树，插入和查询是O(log n)，key 会按顺序排列。
• unordered_map基于哈希表，插入和查询平均是O(1)，key 无序。

本题需要的是快速查询是否存在某个 key，而不是按顺序遍历，所以unordered_map是更合适的选择。用map虽然也能通过，但在大数据量下会慢不少。

Python 则统一用字典dict，底层就是哈希表，没有这个问题。JavaScript 的Map或普通对象也可以，但需要注意Map和普通对象的 key 处理差异，比如对象会把 key 转成字符串。

4.4 空数组和边界条件

如果nums为空数组，我们的代码会直接返回 0，因为循环体不会执行。这个行为是正确的，不需要额外处理。

如果k = 0，代码依然能正确运行，靠的就是“先查后插”的顺序。例如nums = [1, -1], k = 0：

• 遍历到 1：sum = 1，查1 - 0 = 1，哈希表里没有，count = 0；插入{1: 1}。
• 遍历到 -1：sum = 0，查0 - 0 = 0，哈希表里有{0: 1}，count = 1；插入{0: 2}。

答案 1 是正确的，只有一个子数组[1, -1]和为 0，不会把空数组统计进去。

4.5 常见问题速查表

这个表是我在实际刷题和帮别人 review 代码时总结出来的，基本上把这几个问题检查一遍，代码就能稳过。

5. 举一反三：同套路题目的迁移

5.1 力扣 525 连续数组

这道题给定一个二进制数组，要求找到含有相同数量的 0 和 1 的最长连续子数组。解法是把 0 当成 -1，问题就转化为“和为 0 的最长子数组”，这就变成了 560 的变体，只是从计数变成求最长长度。

哈希表里要存的就不只是次数了，而是某个前缀和第一次出现的位置。每遇到一个前缀和sum，如果之前出现过相同的sum，那么从第一次出现的位置到当前位置的子数组和为 0，更新最大长度。这个思路就是 560 的“查历史前缀”思想的迁移。

5.2 力扣 974 和可被 K 整除的子数组

这道题要求统计和为K的倍数（可被 K 整除）的子数组个数。核心转化是把前缀和对K取模，问题变成“前缀和模 K 相同的两个位置之间，子数组和能被 K 整除”。

需要注意负数取模的语言差异：C++ 中负数取模可能得到负数，需要统一转为非负余数，比如((sum % K) + K) % K。这个细节能帮你避开很多“本地跑得通，提交就错”的诡异问题。

5.3 力扣 437 路径总和 III

树上版本的和为 K 子数组问题。二叉树中的任意一条自上而下的路径，统计路径和等于目标值的路径条数。解法就是在 DFS 过程中维护前缀和路径，配合哈希表回溯撤销。根节点到当前节点的路径和减去目标值，如果这个值在哈希表里出现过，说明存在某段路径和为 K。

这个题几乎是 560 的直接移植，只是线性遍历变成了树的 DFS。你可以发现“前缀和 + 哈希表”这个组合非常通用，数组、二进制、取模、树上路径，全都适用。

5.4 怎么识别“前缀和+哈希表”这一类题

我自己的经验是，当你看到以下特征时，优先考虑前缀和加哈希表：

• 题目要求统计连续子数组的个数，或求最长/最短连续子数组的长度。
• 数组元素可能为负数，导致双指针滑动窗口不适用。
• 目标条件可以通过前缀和的差来等价表达，比如sum(i, j) == k等价于prefix[i] == prefix[j + 1] - k。
• 需要在一次遍历中快速查询历史信息，而不关心具体位置时存次数，关心第一次位置时存下标。

6. 我的刷题心得与建议

6.1 这类题目在面试中的考察点

“和为 K 的子数组”是力扣热题 100 中的常客，面试中也经常出现。面试官让你做这题，通常不是考察你知不知道标准答案，而是考察三个能力：

第一，能不能分析暴力解法的瓶颈，并主动提出优化方向。很多候选人上来就写哈希表，问为什么用前缀和却说不太清，这其实是最容易被追问的点。

第二，能不能说清楚prefixCount[0] = 1的含义。这行代码是这道题的灵魂，能讲明白它的含义，说明你真的理解前缀和和空数组之间的关系。

第三，能不能指出为什么不能滑动窗口。如果候选人能主动说“因为数组有负数，破坏了窗口和的单调性”，面试官基本会放心。

6.2 刷题时的个人步骤

我刷这道题和类似题目时，会遵循一个固定流程：

• 先把示例在纸上手动跑一遍暴力解，搞清楚答案是怎么来的。
• 再把暴力解写成代码，提交一次，看看哪里超时，加深对性能瓶颈的感知。
• 然后用前缀和改写，再提交一次，观察复杂度下降但仍然不理想的感觉。
• 最后才上哈希表，一次通过。

这个过程虽然多花时间，但每次都能让我记住这个思路的推导过程。时间是花在刀刃上的，比直接背答案要扎实得多。

这道题的代码很短，短到可能十几行就写完了，但背后的推导链非常长：暴力枚举到前缀和到哈希表优化，每一步都建立在上一步的痛点之上。如果你能完整复述这条链，以后遇到类似问题就不需要死记硬背，而是能从“问题本身需要什么”出发，自己推出解法。