#560 和为 K 的子数组

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

解题思路

主解法

前缀和 + 哈希表

子数组和 = 两个前缀和之差

暴力枚举左右端点再求和是 O(n²) 甚至 O(n³)。用前缀和可以把任意子数组 nums[j..i] 的和写成：

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

也就是在扫描到 i 时，问“前面有多少个前缀和等于 prefix[i] - k”。用哈希表记录每个前缀和出现的次数，就能 O(1) 查到。

自拟主例 nums = [3,1,2,4,-1,2]，k=5。前缀和依次是 3、4、6、10、9、11；当 prefix=9 时查 4（出现 1 次），当 prefix=11 时查 6（出现 1 次），所以答案 2。

分步图解

prefix = 3；prefix - k = -2 出现过 0 次，累计答案 0。

prefix: 3
答案: 0

nums

0

1

2

3

4

5

3

1

2

4

-1

2

i

当前前缀和 3，目标 k = 5

prefix 出现次数

0→1

3→1

用当前前缀和减 k 去查表

1 / 3

前三个前缀和 3、4、6 都查不到 5 的搭档，只负责入表。

两个细节：哈希表要先放入 0 → 1，表示空前缀，否则从下标 0 开始的子数组会漏掉；必须先查再入表，避免把当前前缀自己算进去（k=0 时会多算）。

分步图解

prefix = 10；prefix - k = 5 出现过 0 次，累计答案 0。

prefix: 10
答案: 0

nums

0

1

2

3

4

5

3

1

2

4

-1

2

i

当前前缀和 10，目标 k = 5

prefix 出现次数

0→1

3→1

4→1

6→1

10→1

用当前前缀和减 k 去查表

1 / 4

prefix=9 时查到 4，prefix=11 时查到 6；两个子数组分别是 [2,4,-1] 和 [4,-1,2]。

时间 O(n)，空间 O(n)。数组里有负数也完全没问题，前缀和之差仍然成立。

时间 O(n)空间 O(n)

易错点

忘记 count[0] = 1：从下标 0 开始的子数组全部漏掉。
先 count[prefix]++ 再查 prefix-k：k=0 时会把当前前缀自己算进去。
用滑动窗口处理含负数的数组：窗口和不再单调，收缩条件会失效。

代码与演示

演示输入nums = [3,1,2,4,-1,2], k = 5

空前缀和为 0，先记一次；之后每读一个数，就查 prefix - k 出现过几次。

prefix: 0

nums

0

1

2

3

4

5

3

1

2

4

-1

2

当前前缀和 0，目标 k = 5

prefix 出现次数

0→1

用当前前缀和减 k 去查表

1 / 8

查看 C++ 代码

延伸阅读

前缀和 + 哈希表是“子数组和”问题的通用套路；把和换成余数，就能处理“和能被 k 整除”的题（974）。
如果数组全为正数，滑动窗口也可以做；有负数时只能用前缀和。