LeetCode 560. 和为 K 的子数组
目录
题目描述
题意分析
给定整数数组
nums和整数k，返回和为k的连续子数组的个数。注意求的是个数而不是长度，也不是某一个具体子数组。最关键的约束是数组含负数。这一条直接否掉了滑动窗口：窗口和随右端点扩张不再单调递增，也随左端点收缩不再单调递减，于是「和太大就收缩左边界」这个动作失去依据。例如
nums = [1, -1, 1], k = 1，窗口和会在扩张过程中反复升降，任何单调收缩策略都会漏解。换用前缀和刻画。记
P[t]为前t个元素之和（P[0] = 0），则子数组nums[i..j]的和等于P[j+1] - P[i]。要求它等于k，即P[i] = P[j+1] - k。至此问题完成转化：枚举右边界
j，统计有多少个更早的前缀和恰好等于P[j+1] - k。每一个这样的i都对应一个不同的合法子数组，所以要的是「出现次数」，而不是「是否出现」——这也是本题与两数之和最大的差别，同一个前缀和值可能出现多次，每次都贡献一个答案。
解法：前缀和 + 哈希表计数
核心思路
问题关键：设当前前缀和为
prefix，若更早的前缀和是prefix - k，两者之间的连续子数组和就等于k。因此问题变成：遍历到每个右边界时，统计此前出现过多少个prefix - k。为什么选该解法：双层枚举区间需要 $O(n^2)$；哈希表能在平均 $O(1)$ 时间查到目标前缀和，将总复杂度降到 $O(n)$。数组含负数，窗口和不单调，滑动窗口不可靠。
不变量/状态定义：处理当前元素前，
freq[x]表示所有严格早于当前前缀的、值为x的前缀数量。先用freq[prefix - k]累加答案，再记录当前prefix。初始freq[0] = 1代表空前缀，保证从下标 0 开始的子数组也能被统计。
解题步骤
- 初始化
freq = {0: 1}、prefix = 0、ans = 0。- 遍历数组，将当前元素累加到
prefix。- 将
freq[prefix - k]加入答案。- 执行
freq[prefix]++，供后续位置查询。- 遍历结束后返回
ans。例如
[1,1,1]、k = 2：前缀和依次为 1、2、3，后两次分别命中历史前缀 0、1，答案为 2。
代码实现
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
freq.put(0, 1);
int prefixSum = 0;
int ans = 0;
for (int num : nums) {
prefixSum += num;
// 之前的 prefixSum-k 都可以作为当前子数组的左边界前缀。
ans += freq.getOrDefault(prefixSum - k, 0);
freq.put(prefixSum, freq.getOrDefault(prefixSum, 0) + 1);
}
return ans;
}
}
func subarraySum(nums []int, k int) int {
freq := map[int]int{0: 1}
prefixSum := 0
ans := 0
for _, num := range nums {
prefixSum += num
// 查找能与当前前缀和相差 k 的历史前缀。
ans += freq[prefixSum-k]
freq[prefixSum]++
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，哈希表查询和更新平均为 $O(1)$。
- 空间复杂度：$O(n)$，最坏情况下每个前缀和都不同。
关键点总结
- 前缀和之差把区间计数转成了历史值查询。
- 哈希表必须存出现次数，而不是是否出现或某个下标。
freq[0] = 1覆盖从数组开头起算的子数组。- 必须先查询、后写入，确保左前缀严格早于右前缀。
易错点总结
- 使用滑动窗口：
[1,-1,0]、k = 0中窗口和不单调，会漏解。- 漏掉
freq[0] = 1：[3]、k = 3会错误返回 0。- 先写入再查询：当
k = 0时会把空子数组计入。- 命中时只执行
ans++：[1,-1,0]、k = 0有重复前缀，正确答案是 3。- 将哈希值存为下标：本题求数量，必须保存每个前缀和的出现次数。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 325. 和等于 k 的最长子数组长度 | 中等 | 由计数改成求最长，哈希改存前缀和首次出现的下标 |
| 525. 连续数组 | 中等 | 把 0 视作 -1，转成求和为 0 的最长子数组 |
| 974. 和可被 K 整除的子数组 | 中等 | 按前缀和的模 K 余数分组计数，注意负数取模要修正 |
| 523. 连续的子数组和 | 中等 | 同样按余数判定，但只问存在性且要求长度至少为 2 |
| 930. 和相同的二元子数组 | 中等 | 元素非负，除本解法外还可用「至多 sum」相减的双指针 |
| 1248. 统计「优美子数组」 | 中等 | 奇数记 1、偶数记 0，转成和恰为 k 的子数组计数 |
| 1074. 元素和为目标值的子矩阵数量 | 困难 | 枚举上下边界把矩阵压成一维，再对每种边界套用本题 |
| 437. 路径总和 III | 中等 | 前缀和搬到树上，回溯返回时必须撤销当前前缀的计数 |
| LCR 010. 和为 K 的子数组 | 中等 | 与本题同题，可直接套用 |
| LCR 011. 连续数组 | 中等 | 与 525 同题，0/1 数组的等价转化 |
| 面试题 17.05. 字母与数字 | 中等 | 字母记 +1、数字记 -1，求和为 0 的最长子数组 |