LeetCode 560 Subarray Sum Equals K 题解：前缀和 + 哈希表统计子数组和等于 k 的个数
【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode
本篇技术指南围绕 LeetCode 560「和为 K 的子数组」（Subarray Sum Equals K）展开，完整讲解从暴力枚举到"前缀和 + 哈希表"的两种解法、复杂度分析与常见陷阱，并结合当前仓库中 Python、C++、C、Java、Go、Rust、JavaScript、TypeScript、Kotlin、Swift 等 10 种语言的实现源码进行印证。读完本文，你将掌握如何用 O(n) 时间统计"和为 k 的连续子数组个数"，并能正确应对负整数、k = 0等边界场景。
前置知识
在动手解决本题之前，建议先熟悉以下两个基础工具：
- 前缀和（Prefix Sum）：最优解依赖的核心性质——任意子数组的和都可以由两个前缀和相减得到。定义
prefixSum[i]为数组前i个元素之和，则下标从i+1到j的子数组和为prefixSum[j] - prefixSum[i]。 - 哈希表（Hash Map）：用于存储"前缀和 → 出现次数"的映射，实现在遍历过程中 O(1) 查询互补值
curSum - k。
解法一：暴力枚举（Brute Force）
思路
最朴素的做法是枚举每一个可能的子数组，检查其和是否等于k。对每个起始下标i，我们逐元素向右扩展子数组，同时维护一个运行中的累加和sum；每当sum == k就计数一次。注意本题要求的是连续子数组，因此只需要双重循环即可覆盖所有区间。
算法步骤
- 初始化
res = 0。 - 对每个起始下标
i：- 重置
sum = 0。 - 对每个结束下标
j（从i到n - 1）：- 将
nums[j]累加到sum。 - 若
sum == k，res加一。
- 将
- 重置
- 返回
res。
复杂度分析
- 时间复杂度：$O(n ^ 2)$，枚举了所有 $\frac{n(n+1)}{2}$ 个子数组。
- 空间复杂度：$O(1)$，只使用了常数个变量。
暴力法虽然直观，但当n达到 $10^5$ 量级时 $O(n^2)$ 必然超时，因此需要更优的解法。
解法二：前缀和 + 哈希表（Hash Map）
思路
核心洞察是：若prefixSum[j] - prefixSum[i] = k，则从下标i+1到j的子数组和为k。于是问题转化为：遍历到每个位置j时，统计此前有多少个位置i的前缀和等于curSum - k。用一个哈希表记录每个前缀和出现的次数，即可在 O(1) 时间内完成查询。
算法步骤
- 初始化
res = 0、curSum = 0，以及哈希表prefixSums，并预置{0: 1}（表示空前缀，前缀和为 0 出现一次）。 - 遍历数组中的每个数：
- 将其累加到
curSum。 - 计算
diff = curSum - k。 - 将
prefixSums[diff]（即此前出现过diff这个前缀和的次数）累加到res——这统计的是以当前位置结尾、和为k的子数组个数。 - 将
prefixSums[curSum]加一，记录当前前缀和。
- 将其累加到
- 返回
res。
复杂度分析
- 时间复杂度：$O(n)$，数组只遍历一遍，每次哈希表操作均为 O(1) 摊还。
- 空间复杂度：$O(n)$，哈希表最多存储
n + 1个不同的前缀和。
各语言实现对照
本仓库在 10 种语言中提供了该解法的实现，核心逻辑完全一致，可直接对照学习：
- Python：python/0560-subarray-sum-equals-k.py 使用字典
dic = {0: 1}预置空前缀，遍历时先查sum - k再更新dic[sum]，并注明 O(N) 时间、O(N) 空间。 - C++：cpp/0560-subarray-sum-equals-k.cpp 使用
unordered_map<int,int>，注意其额外在sum == target时直接对count加一，与mp[sum - target]的统计逻辑等价（因为mp[0]尚未初始化时默认计数缺失，需依赖预置的mp[0]；实际上该实现以sum == target显式补上"从下标 0 开始的子数组"这一情况）。 - C：c/0560-subarray-sum-equals-k.c 展示了不依赖标准库哈希表时的完整手写实现：定义
Hash链地址法结构体，INIT_HASH_SIZE 4096作为桶数，HashKey通过取模把负前缀和归一化到桶内，AddHash处理冲突、GetHash未命中返回 0，主函数subarraySum同样先AddHash(hash, 0)预置空前缀，再"先查后插"。这段代码对理解哈希表底层原理很有价值。 - Java：java/0560-subarray-sum-equals-k.java 使用
HashMap<Integer, Integer>，getOrDefault(diff, 0)处理缺失键。 - Go：go/0560-subarray-sum-equals-k.go 用字面量
map[int]int{0: 1}初始化。 - Rust：rust/0560-subarray-sum-equals-k.rs 用
HashMap::with_capacity(nums.len() / 2)预分配容量，entry(...).and_modify(...).or_insert(1)完成计数更新。 - JavaScript：javascript/0560-subarray-sum-equals-k.js 与TypeScript：typescript/0560-subarray-sum-equals-k.ts 使用
Map，以map.get(sum) || 0处理缺省值。 - Kotlin：kotlin/0560-subarray-sum-equals-k.kt 使用
hashMapOf(0 to 1)与getOrDefault。 - Swift：swift/0560-subarray-sum-equals-k.swift 使用字典
[0: 1]与hashmap[diff, default: 0]。
从上述实现可以看到，无论语言如何，算法骨架完全一致：预置{0: 1}→ 累加curSum→ 查询curSum - k→ 更新curSum计数。
常见陷阱（Common Pitfalls）
陷阱一：忘记用零初始化哈希表
哈希表必须以{0: 1}作为初始状态，用于处理从下标 0 开始的子数组。如果没有这一初始化，那么"从头开始的、前缀和恰好等于k"的子数组将永远无法被计数。例如nums = [3, 4, 7, 2]、k = 7：遍历到下标 1 时curSum = 7，需要diff = 0存在才会计数[3, 4]这个子数组；{0: 1}正是提供这个基准。
陷阱二：试图使用滑动窗口（Sliding Window）
与"乘积小于 K 的子数组"这类单调性问题不同，本题数组允许出现负数，运行中的累加和并不单调：收缩窗口可能让和变大也可能变小，无法确定性地维护窗口。因此滑动窗口在这里失效，必须采用"前缀和 + 哈希表"的方案。
陷阱三：先更新哈希表再查询
操作的顺序至关重要：必须先检查curSum - k是否在哈希表中，然后再把curSum写入哈希表。若顺序颠倒，当前元素会被错误地当作"之前出现过的前缀和"参与计数，导致统计偏差。以k = 0的场景为例：若先写入curSum再查询curSum - 0 = curSum，会把"空子数组"也计入结果，得到错误答案。
举一反三：边界与变式
k = 0且数组含零：nums = [1, -1, 0]、k = 0时，正确答案为 3（子数组[1, -1]、[0]、[1, -1, 0]）。用哈希表方案手工推演一遍即可验证{0: 1}初始化与"先查后插"顺序的必要性。- 答案上限：子数组个数最多为 $\frac{n(n+1)}{2}$，当数组元素全为 0 且
k = 0时达到该上限，因此res在 LeetCode 约束下需用int表示（Python 无此顾虑）。 - 变式延伸：同一套"前缀和 + 哈希表"思路稍加改造即可迁移到 subarray-sums-divisible-by-k（改为对
k取模）、continuous-subarray-sum（查找长度 ≥ 2 的倍数子数组）等题目，值得一并练习。
小结
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力枚举 | $O(n^2)$ | $O(1)$ | 数组规模小、仅用于理解题意 |
| 前缀和 + 哈希表 | $O(n)$ | $O(n)$ | 大规模数组，含负数，标准解法 |
Subarray Sum Equals K 是"前缀和 + 哈希表"这一经典组合的入门必刷题：它把一个看似需要枚举所有子数组的问题，转化为"统计互补前缀和出现次数"的线性扫描问题。掌握{0: 1}初始化、先查询后更新这两个关键点，并理解为什么负数使滑动窗口失效，你就真正吃透了这道题，也能为后续的子数组类问题打下坚实基础。
【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
