和为K的子数组：前缀和+哈希表优化详解

LeetCode Hot 100 里的第560题“和为K的子数组”，是我刷题过程中印象很深的一道题。题目本身只有一句话：给定一个整数数组和一个整数K，统计数组中有多少个连续子数组的和等于K。读完感觉很简单，但真动笔写，很多人会发现自己要么写出O(n³)的暴力循环，要么在负数和零面前栽跟头。这道题真正想考察的，不是你会不会写循环，而是你对“前缀和 + 哈希表”这套组合技有没有吃透。

这道题建议所有准备算法面试的朋友都花时间认真拆一遍。它表面是计数题，实际上涉及几个很核心的算法思维：暴力枚举怎么一步步优化、什么时候不能用滑动窗口、哈希表里存什么才能把时间复杂度从O(n²)降到O(n)。如果你能把这道题的来龙去脉讲清楚，面试里遇到类似“连续子数组 + 条件计数”的题，基本都能顺手解掉。

1. 先搞清楚题目在问什么

1.1 一个看似简单的统计问题

题目给的数组是整数数组，注意是“整数”，不是“正整数”。这意味着数组里可能包含负数、零，也可以全是一样的数字。要求统计的是连续子数组，所谓连续子数组，就是原数组中连续的一段，比如nums[2]到nums[5]这样夹出来的一块。每个子数组可以只有一个元素，也可以是整个数组，甚至数组里每个单独的元素只要等于K，都算一个满足条件的子数组。

举个例子，数组[1, 1, 1]，K=2，答案是2。哪两个呢？第一个子数组是[1, 1]（下标0到1），第二个是[1, 1]（下标1到2）。这两个子数组虽然长得一样，但因为位置不同，是两条不同的子数组，所以计数2。这一点很重要，暴力和前缀和方案都要确保把这种“位置不同就算不同子数组”的情况算进去。

1.2 连续子数组的两个隐蔽陷阱

第一个陷阱是“连续”两个字。很多新手一开始会去想组合数学，试图用排列组合的方式算出多少个和等于K，然后就被绕晕了。但其实连续子数组不关心元素怎么排，它只关心原数组中一段一段的窗口，每段就是一个连续区间，所以问题的本质是：有多少个区间[i, j]满足下标从 i 到 j 的所有元素和正好等于K。

第二个陷阱是数组里有负数。负数会让“当前累加和”变得不单调。你从前往后累加，可能加了几个正数后遇到一个很大的负数，和一下子掉下来，然后又升上去。这种非单调性直接堵死了一条很多人第一反应会走的路：滑动窗口。

1.3 为什么滑动窗口在这道题上会失效

滑动窗口（双指针）是处理连续子数组求和的经典工具，比如“和无大于等于target的最短子数组”这类题。它之所以高效，是因为窗口右边界往右扩展时，窗口和变大；左边界往右缩时，窗口和变小。这个单调性保证了你移动指针的每一步都有明确方向。

但一旦数组里出现负数，这个前提就破了。右指针往右走，窗口和可能变小；左指针往右走，窗口和可能变大。这种情况下你没法确定该挪哪个指针，即使挪对了也无法保证不会漏掉解。我见过不少人在这道题上试着用滑动窗口写，写了半天发现样例都过不了，最后才意识到负数把单调性破坏掉了。

2. 从暴力到优雅：优化路径拆解

2.1 三层循环的暴力枚举

最直觉的写法是枚举所有子数组。一个子数组由起点和终点决定，所以我们可以写两层循环确定起点和终点，然后第三层循环从起点加到终点，计算总和。

def subarraySum(nums, k): n = len(nums) count = 0 for i in range(n): for j in range(i, n): total = 0 for m in range(i, j + 1): total += nums[m] if total == k: count += 1 return count

三层循环，最内层每次重新加一遍，时间复杂度O(n³)。这个版本我一般不建议你真正提交，它存在的意义是帮你确认自己理解了题意：子数组是连续区间，位置不同就算不同。三个循环分别对应“起点”、“终点”、“求和”，逻辑很直白，但效率极其低下，n稍微大一点（比如500以上）就会超时。

2.2 固定起点累加的O(n²)优化

三层循环最蠢的地方在于，每次内层都从零开始加。其实我们固定起点i之后，让终点j不断往右走，同时用一个变量维护当前这段的和，就不需要第三层循环了。

def subarraySum(nums, k): n = len(nums) count = 0 for i in range(n): total = 0 for j in range(i, n): total += nums[j] if total == k: count += 1 return count

这个版本是O(n²)，已经是很多人的第一版“能过一部分样例”的代码。它的核心思想是：固定每个起点i，然后依次增加终点j，实时维护从i到j的区间和。每个片段的和只需要在上一个片段基础上加一个元素，不用重新算。不过当n达到10⁵级别时，O(n²)依然会超时，LeetCode的测试用例显然会把它卡掉。

2.3 暴力法的复杂度画像与瓶颈

暴力法慢在哪？慢在我们在反复求“从i到j这一段的和”。即使优化到O(n²)，依然有太多冗余计算：不同的起点和终点组合成大量区间，很多区间是重叠的，它们的和信息被反复计算。比如求nums[1..5]的和，和求nums[1..4]的和只有最后一个元素不同，但每次都要重新累加。

这说明我们需要一种方式，能快速算出任意区间的和，而不是每次从头加到尾。这时候前缀和就该登场了。前缀和的核心思想是：提前算好“从数组开头到每个位置”的累计和，那么任意区间[i, j]的和，就等于pre[j+1] - pre[i]，直接两个数相减，O(1)拿到结果。

3. 前缀和 + 哈希表：O(n)解法全解析

3.1 前缀和的数学表达

定义前缀和数组pre，其中pre[i]表示原数组nums[0..i-1]所有元素的和，也就是“前i个元素的和”。特别地，pre[0] = 0，代表一个元素都不取时的和。

有了这个定义，任意一个子数组nums[i..j]的和可以表示为：

subarray_sum(i, j) = pre[j+1] - pre[i]

我们要找的是subarray_sum(i, j) == k，代入就变成：

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

移项：

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

这个移项是整个题目的灵魂。它把“找区间和等于K”的问题，变成了“找两个前缀和之间的差值等于K”的问题。也就是说，当我们遍历到右端点j（对应前缀和位置j+1）时，只需要看看之前有没有出现过值为pre[j+1] - k的前缀和。如果有，每出现一次，就说明有一个左端点 i 能和当前右端点组成一个满足条件的子数组。

3.2 哈希表里存的是“次数”而非“下标”

很多做“和为K的最长子数组”（LeetCode 325）的朋友会习惯性在哈希表里存下标，但这道题要存的是次数。因为题目只问有多少个子数组，不问最长或最短，所以对于某个前缀和值，我们只关心它出现过几次，不关心它第一次出现在哪。

为什么是次数？假设当前前缀和是pre，我们想找有没有pre - k出现过。如果pre - k出现过3次，那就意味着有3个不同的左端点能和当前右端点构成合法的子数组。这3个子数组的区间不同，都要计入答案，所以哈希表的值必须是次数。

def subarraySum(nums, k): mp = {0: 1} pre_sum = 0 count = 0 for num in nums: pre_sum += num count += mp.get(pre_sum - k, 0) mp[pre_sum] = mp.get(pre_sum, 0) + 1 return count

核心就三行逻辑：累加当前前缀和，查哈希表找pre_sum - k的计数并累加到答案，再把当前前缀和的出现次数加一。整个遍历一趟数组，时间复杂度O(n)，空间复杂度O(n)。

3.3 手推示例：nums=[1,1,1] 的全过程

光看代码不够，我建议你亲手推一遍。以nums = [1, 1, 1]，k = 2为例：

• 初始化：mp = {0: 1}，pre_sum = 0，count = 0
• 第一个元素1：pre_sum = 1，查mp[1-2] = mp[-1]，不存在，于是count = 0。更新mp[1] = 1，此时mp = {0:1, 1:1}
• 第二个元素1：pre_sum = 2，查mp[2-2] = mp[0]，存在且为1，count = 1。更新mp[2] = 1
• 第三个元素1：pre_sum = 3，查mp[3-2] = mp[1]，存在且为1，count = 2。更新mp[3] = 1

最终返回2，和预期一致。注意到第二个元素时查到的mp[0]对应的左端点是“空前缀”，也就是从数组开头到当前位置的整个子数组，这正说明初始化mp[0] = 1是必须的。

再推一个带负数的例子：nums = [1, -1, 0]，k = 0。这个例子能同时验证负数场景和连续0的情况，答案是3：[1, -1]、[0]、[1, -1, 0]。

• 初始化：mp = {0: 1}，pre_sum = 0，count = 0
• 第一个元素1：pre_sum = 1，查mp[1-0] = mp[1]，无，count = 0。更新mp[1] = 1
• 第二个元素-1：pre_sum = 0，查mp[0-0] = mp[0]，有1，count = 1（这里对应子数组[1,-1]）。更新mp[0] = 2
• 第三个元素0：pre_sum = 0，查mp[0-0] = mp[0]，有2，count = 3（对应子数组[0]和[1,-1,0]）。更新mp[0] = 3

完美得到3。这里的第二个元素处，如果初始mp[0]不是1，就会漏掉[1,-1]这个从开头开始的子数组。第三个元素处利用mp[0] = 2一次统计了两条子数组，效率非常高。

3.4 关键细节：为什么“先查询，后更新”

这是这道题最容易被忽略的细节。每遍历一个元素，必须先查mp[pre_sum - k]，然后才能把当前pre_sum计数的频率加一。如果你反过来，先更新mp[pre_sum]再查询，会导致什么样的后果？

当k = 0时，pre_sum - k恰好等于pre_sum。如果你先把当前pre_sum加进哈希表再查询，就会把“当前这个前缀和自身”也当成一个答案统计进去。但当前这个位置还没结束，它不能既当左端点又当右端点。举最极端的例子：nums = [2]，k = 0。正确答案是0，因为没有任何子数组和为0。但如果你先更新再查询：pre_sum = 2，mp[2] = 1，查mp[2-0] = 1，得到count = 1，直接算错了。

“先查后更新”本质上是保证左右端点不能重合。查询时，哈希表里只包含当前元素之前的前缀和，这才能保证左端点 i 严格小于当前右端点 j。

4. 边界情况与实战坑位

4.1 K=0时最容易漏统计的场景

上一节提到了k = 0的情况，这里再展开说透。当K等于0时，题目变成：有多少个子数组的和等于0。因为零的特殊性，答案常常比直觉多很多。

比如nums = [0, 0]，K=0，正确答案是3：两个单独为0的子数组，加上整个数组[0,0]。用哈希表方案可以轻松算出来。但如果你是手动模拟暴力，很可能只数出2个。这个例子也很适合拿来测试你自己的写法：如果输出1或2，说明你的初始化或更新逻辑有问题。

注意：K=0时，pre_sum - k等于pre_sum本身，这要求查询时绝对不能把当前刚更新的前缀和算进去。一旦先更新再查询，错误会立刻暴露。

4.2 负数与零对前缀和的影响

负数导致前缀和不单调，这是滑动窗口失效的根源。零则导致前缀和可能出现连续重复值，这对计数没有坏处，因为重复值越多，哈希表里mp[pre_sum]越大，后面遇到匹配时能一次性统计更多答案。

但重复前缀和也会让一个直觉性结论变得反直觉：一个子数组的和为0，不一定是[0]或[1,-1]这样的直观组合，它可能藏在连续多个0里，比如[0,0,0]的子数组和为0的有6条。哈希表方案的好处是，遇到重复的pre_sum，直接把计数累加进哈希表，后续匹配时一次拿全，不会漏。

4.3 细节决定成败：初始值、变量类型与语言陷阱

初始化mp = {0: 1}的作用是支持“从数组开头开始的子数组”。任何前缀和pre_sum - k = 0的情况，都意味着存在一个从下标0开始到当前右端点结束的子数组。如果不初始化，这样的子数组会被全部漏掉，而且在K=0时错误尤其隐蔽。

变量类型方面，Python的int是任意精度，不需要担心溢出。但如果你用Java或C++，前缀和累加可能会超过int范围。数组长度最大是2 * 10⁵，每个元素绝对值最大10⁴，前缀和绝对值最大能到2 * 10⁹，虽然int最大约2.1 * 10⁹，看起来刚好卡在边界，但多个累加中间过程可能超过，稳妥起见建议直接用long。LeetCode原题的函数签名返回int，但累加变量pre_sum和答案count都应该用更大的类型，Java用long和long，C++用long long。

注意：答案可能超过int范围。极端情况下数组全为0，K=0，子数组数量是 n * (n+1) / 2，n=210⁵ 时大约210¹⁰，远超int范围。Python没有这个问题，Java和C++需要特别留意答案类型。

5. 变体与面试延伸

5.1 如果面试官要求输出所有满足条件的子数组

有时候面试官会在你写完后追问：能不能把所有满足条件的子数组打印出来？这时候哈希表里存的就不能只是次数了，而是一个数组，记录每个前缀和出现过的下标。

基本思路：mp[pre_sum]改成mp[pre_sum] = [下标列表]。遍历时，查到pre_sum - k对应的下标列表后，列表里每个下标 i 都和当前右端点构成一个合法子数组nums[i+1..j]。注意当前pre_sum对应的右端点下标是j，而pre_sum本身是在元素nums[j]累加后得到的，所以区间起点是i+1，终点是j。

def subarraySumDetails(nums, k): mp = {0: [-1]} pre_sum = 0 res = [] for j, num in enumerate(nums): pre_sum += num target = pre_sum - k if target in mp: for i in mp[target]: res.append((i + 1, j)) mp.setdefault(pre_sum, []).append(j) return res

注意这里初始化{0: [-1]}，因为前缀和pre[0]对应“一个元素都不取”，当我们需要i = -1时，子数组从下标0开始。这个变体是很好的加分项，面试官能看出你是真的理解了这个方法，而不是背代码。

5.2 与同类题目的对比：974、325、862

面试中，面试官很可能借这道题引出一系列姊妹题。我整理过一个对比清单，这里分享给你：

974题与560几乎同构，只差一个取模。要注意的是负数取模在不同语言里行为不同，C++中(-5) % 3 = -2，需要写成((pre_sum % k) + k) % k统一余数范围。这些姊妹题能让你形成完整的知识网络，遇到类似题时能迅速识别模式。

5.3 这道题在工作场景中的映射

很多朋友问算法题到底有什么用，其实前缀和思想在工程里非常常见。比如分析交易流水，想知道有多少个连续时间段内的累计交易额正好等于某个目标值；或者分析日志数据，找出一段连续请求量的和是否命中某个阈值。这些场景本质上都是“区间求和 + 条件计数”。

更进一步，任何需要频繁计算任意区间和的场景，前缀和都是利器。预计算一遍前缀和数组，之后每次区间查询都是O(1)的减法操作。这在报表系统、数据分析和监控告警系统中都很实用。

6. 踩坑记录与个人心得

6.1 我实际提交时遇到过的错误

第一次写这道题，我犯过三个典型错误，每个都值得拿出来说。

第一个是忘记初始化mp[0] = 1，结果所有从下标0开始的子数组全部漏掉。当时我用nums = [3, 4, 7, 2, -3, 1, 4, 2]这样的用例测试，一直少算了[3, 4]这样的开头子数组，查了十几分钟才发现哈希表里根本没有0。

第二个是只想着存下标，写成了mp = {0: -1}，然后试图用j - i来计数，写出来的代码又臭又长，还漏了重复前缀和的情况。后来才意识到这道题根本不需要下标，存次数就够了。

第三个是在处理负数取模的时候，一开始没把余数归一，导致974题怎么都不对。从那以后我养成了一个习惯：遇到取模运算，先确认负数的语义。

6.2 解题前必做的“三问”

现在我做连续子数组求和类的题目，动笔之前会先做三个自问自答：

一，数组里有没有负数？有负数，滑窗基本可以排除；无负数，滑窗可以作为一个候选方案。 二，题目要的是计数、最长、最短，还是打印所有子数组？这决定了哈希表里存次数、最早下标还是下标列表。 三，当前遍历位置能否参与答案统计？也就是“先查后更新”的顺序问题。这个顺序在所有类似题目里都要留意，不只是K=0时才需要。

这套三问法让我少踩了很多坑，也让我在面试时能更清晰地给面试官讲思路。

6.3 最后一点经验

回过头看，560这道题难吗？知识点本身不难，前缀和和哈希表都是基础内容。但它之所以被放进Hot 100，我猜是因为它把“连续区间求和”“哈希表优化”“边界条件处理”三个高频考点浓缩到了一道题里。你能不能在紧张的环境下一步步推导出O(n)方案，能不能正确处理负数和零，能不能讲清楚先查后更新的道理，往往比代码本身更能反映水平。

我自己后来刷题时，只要遇到“连续子数组 + 和/积 + 计数”的组合，第一反应就是先想想能不能用前缀和，如果题目允许负数和零，基本上可以确定哈希表方案是正解。这个条件反射帮我解决了不少Hard题的基础版本。希望你也能通过这道题，把前缀和 + 哈希表这套思路真正变成自己的东西。