和为 K 的子数组:前缀和与哈希表组合技 —— LogicStack-LeetCode 刷穿 LeetCode 560 题深度解析
和为 K 的子数组:前缀和与哈希表组合技 —— LogicStack-LeetCode 刷穿 LeetCode 560 题深度解析
本文是 LogicStack-LeetCode(公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列)中 LeetCode 560 号题「和为 K 的子数组」的完整技术解析。文章以仓库内 560. 和为 K 的子数组(中等).md 为主体,结合仓库中「前缀和」「哈希表」两大算法索引,讲解如何在 O(n) 时间内统计数组中和为 k 的连续子数组个数,并延伸探讨该思路在二维矩阵、树上路径等场景中的统一应用。读完你将掌握「前缀和 + 哈希表」这一高频组合技巧的本质推导、多语言实现细节及其变体题的通解思路。
题目描述
这是 LeetCode 上的 560 号题「和为 K 的子数组」,难度为中等,核心 Tag 为**「前缀和」与「哈希表」**。
给你一个整数数组
nums和一个整数k,请你统计并返回该数组中和为k的子数组的个数。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
示例 2:
输入:nums = [1,2,3], k = 3
输出:2
数据范围(即本题的约束前提,也是选择算法的依据):
1 <= nums.length <= 2 × 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
注意两点关键信息:其一,nums[i] 可为负数,因此不能用「双指针/滑动窗口」这类依赖单调性的做法;其二,n 最大为 2 × 10^4,朴素的 O(n^2) 枚举所有子数组并求和(O(n^3) 更不必说)在数据量较大时会超时,必须将复杂度优化到 O(n)。
为什么朴素枚举不可行
最直观的思路是枚举每个子数组的起点与终点,再累加求和判断是否等于 k。但子数组个数为 O(n^2),如果每次求和都重新累加,总复杂度为 O(n^3);即便用「增量求和」技巧,也只能降到 O(n^2),在 n = 2 × 10^4 时计算量达到约 4 × 10^8,处于超时边缘。
由于数组元素存在负数,子数组和并不随长度单调变化,「滑动窗口」这一经典优化手段在此题中失效。 因此需要引入前缀和,把「区间和」的求解从每次 O(区间长度) 降为 O(1),再配合哈希表把「查找」也降到 O(1),从而整体达到线性复杂度。
核心思路:前缀和 + 哈希表
1. 前缀和的定义
预处理一个前缀和数组 sum(下标默认从 1 开始),其中:
sum[i] = nums[0] + nums[1] + ... + nums[i-1]
即 sum[i] 表示原数组前 i 个元素的和。这样任意区间 [l, r](原数组下标从 0 计)的和都可以表示为:
sum[r + 1] - sum[l]
一次 O(n) 的预处理,即可在 O(1) 时间内回答任意区间和。
2. 统计「以每个位置为结尾」的合法子数组
原文档给出的关键洞察是:统计以每一个 nums[i] 为结尾、和为 k 的子数组数量,加总即是答案。
对于以原数组第 i 个元素(即前缀和下标 i)为结尾的子数组,其可能的左端点范围为 [0, i](对应前缀和下标 [0, i])。若子数组 [l, i] 的和为 k,则等价于:
sum[i + 1] - sum[l] = k ⟹ sum[l] = sum[i + 1] - k
因此问题转化为:在遍历到前缀和下标 i 时,sum[0..i] 中有多少个位置的值等于 sum[i + 1] - k。
3. 用哈希表同步记录前缀和出现次数
为了在 O(1) 时间内回答「有多少个历史前缀和等于 target = sum[i + 1] - k」,可以在遍历过程中用哈希表 map 同步维护「每个前缀和值出现的次数」。
细节一:初始化 map[0] = 1。 前缀和 sum[0] = 0 代表「空前缀」,它对应左端点 l = 0(即子数组从原数组开头取起)。若某次 sum[i + 1] - k = 0,说明 [0, i] 这个整段前缀本身就是合法子数组,必须在初始化时就把 0 计入哈希表才能正确统计。
细节二:先查询、后更新。 对于每个 i,应当先查询 map[sum[i + 1] - k] 累加进答案,再把当前的 sum[i + 1] 计数加一。如果先更新再查询,就会把「以当前元素为结尾、长度为 0」的空子数组也统计进去,造成错误计数。
细节三:getOrDefault 与 find 的写法。 查询一个不存在的键时,Java 用 map.getOrDefault(d, 0) 返回默认值 0;C++ 需先用 map.find(d) != map.end() 判断存在再累加;Python 的 defaultdict(int) 访问不存在的键会自动返回 0。
多语言实现(完整可运行代码)
以下四段代码均来自原文档,可直接在 LeetCode 或本地调试环境运行:
Java
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length, ans = 0;
int[] sum = new int[n + 10];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int i = 1; i <= n; i++) {
int t = sum[i], d = t - k;
ans += map.getOrDefault(d, 0);
map.put(t, map.getOrDefault(t, 0) + 1);
}
return ans;
}
}
C++
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
vector<int> sumv(n + 1, 0);
for (int i = 1; i <= n; i++) sumv[i] = sumv[i - 1] + nums[i - 1];
unordered_map<int, int> map;
map[0] = 1;
for (int i = 1; i <= n; i++) {
int t = sumv[i], d = t - k;
if (map.find(d) != map.end()) ans += map[d];
map[t]++;
}
return ans;
}
};
Python
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
n, ans = len(nums), 0
sumv = [0] * (n + 10)
for i in range(1, n + 1):
sumv[i] = sumv[i - 1] + nums[i - 1]
mapping = defaultdict(int)
mapping[0] = 1
for i in range(1, n + 1):
t = sumv[i]
d = t - k
ans += mapping[d]
mapping[t] += 1
return ans
TypeScript
function subarraySum(nums: number[], k: number): number {
let n = nums.length, ans = 0
const sum = new Array<number>(n + 10).fill(0)
for (let i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1]
const map = new Map<number, number>()
map.set(0, 1)
for (let i = 1; i <= n; i++) {
const t = sum[i], d = t - k
if (map.has(d)) ans += map.get(d)
map.set(t, map.has(t) ? map.get(t) + 1 : 1)
}
return ans
};
注:上述代码为原文档实现,前缀和数组多申请了
n + 10的长度,属于「哨兵余量」的稳健写法;若追求最小内存,改为n + 1完全等价。
复杂度分析
- 时间复杂度:预处理前缀和数组为
O(n),单次遍历配合哈希表统计答案为O(n),整体复杂度O(n)(哈希表读写均摊O(1))。 - 空间复杂度:前缀和数组与哈希表各占用
O(n)空间,整体O(n)。
相比朴素枚举的 O(n^2) 甚至 O(n^3),这一解法在数据范围上限(n = 2 × 10^4)下表现稳健,这正是它成为「前缀和经典应用题」的原因。
为什么 map[0] = 1 必不可少:一个推演示例
以示例 nums = [1,1,1], k = 2 手动推演一遍流程,可以直观理解「先查询、后更新」与 map[0] = 1 的作用:
| 前缀和下标 i | sum[i] | 查询目标 sum[i] - k | 命中次数 | 累计 ans | 更新 map |
|---|---|---|---|---|---|
| 0 | 0 | - | - | 0 | {0:1} |
| 1 | 1 | -1 | 0 | 0 | {0:1, 1:1} |
| 2 | 2 | 0 | 1(空前缀) | 1 | {0:1, 1:1, 2:1} |
| 3 | 3 | 1 | 1(前缀下标1) | 2 | {0:1, 1:1, 2:1, 3:1} |
最终 ans = 2,对应子数组 [1,1](下标 0-1)与 [1,1](下标 1-2),与预期一致。注意第二次命中依赖的是哈希表中早已存在的前缀和 sum[1] = 1,这正体现了「先查询再更新」的顺序正确性。
仓库中的同类题与通解体系
本题是「前缀和 + 哈希表」组合的基石题,LogicStack-LeetCode 仓库在 Index/前缀和.md 与 Index/哈希表.md 两个算法索引中均有收录(推荐指数 🤩🤩🤩🤩🤩),并在多个系列题解中反复使用同一套路:
- 剑指 Offer II 010. 和为 k 的子数组(中等):与本题完全相同的题目与解法(仓库内代码为 Java 与 TypeScript 双版本),适合作为同一思路的对照复习。
- 523. 连续的子数组和(中等):把「等于 k」改为「是 k 的倍数」。关键推导为
sum[j] - sum[i-1] = n×k等价于sum[j] ≡ sum[i-1] (mod k),于是只需用HashSet记录「前缀和对 k 的取余结果」,并注意子数组长度至少为 2(循环从i = 2开始、延迟一个位置插入哈希表)。这是「前缀和 + 哈希」思路在模运算维度上的自然延伸。 - 437. 路径总和 III(中等):把一维数组换成「二叉树中的向下路径」。由于根到任意节点的路径唯一,统计「以每个节点为结尾、和为 targetSum 的路径数」本质上就是一个一维前缀和问题;唯一需要注意的是回溯时把当前前缀和从哈希表中删除,防止统计到跨越左右两个方向的非法路径。
- 1074. 元素和为目标值的子矩阵数量(困难):将本题推广到二维。先做二维前缀和,然后枚举子矩阵的上下边界,在右边界右移的过程中把「右边界到原矩阵左边界」的矩阵和存入哈希表,再用
cur - target查找合法的左边界,从而把O(n^4)的朴素枚举优化到O(m × n^2)。
可以清晰看到一条方法论主线:凡是「统计连续区间/路径/子矩阵的和等于某值」的问题,都可以尝试「前缀和预处理 + 哈希表查历史」来把枚举配对降为线性或准线性复杂度。本题正是这一通解的最小、最干净的载体。
小结
560 号题是「前缀和 + 哈希表」组合技巧的入门必刷题:
- 因为元素可正可负,滑动窗口失效,必须使用前缀和把区间和降为
O(1)查询; - 统计「以每个位置结尾的合法子数组数」并累加,是避免重复枚举左右端点的关键视角;
- 哈希表同步记录历史前缀和出现次数,配合
map[0] = 1与「先查询、后更新」两个细节,即可在O(n)时间内完成统计; - 该套路可自然推广到「模 k 同余」(523)、「树上前缀和」(437)、「二维子矩阵」(1074)等系列变体,值得作为模板反复演练。
需要更多同类练习时,可回到仓库的 Index/前缀和.md 与 Index/哈希表.md 按推荐指数挑选题目,形成「一题入门、多题巩固、变体检验」的完整刷题闭环。