和为 K 的子数组
Subarray Sum Equals K
本机进度仅保存在当前浏览器
题目描述
给你一个整数数组 nums 和一个整数 k，请统计并返回该数组中「和恰好为 k」的连续子数组的个数（数组可能含负数）。
示例：nums = [1, 1, 1]，k = 2，输出 2；nums = [1, 2, 3]，k = 3，输出 2（[1,2] 与 [3]）。
解题思路
- 含负数时窗口单调性失效，滑动窗口不可用；转用前缀和：区间 [i, j] 的和 = prefix[j] - prefix[i-1]。
- 要统计和为 k 的区间数，等价于对每个 j 统计有多少个前缀值等于 prefix[j] - k。
- 用哈希表统计每个前缀和出现的次数，边扫边查、边存，一遍完成。
- 初始时前缀和 0 出现一次（空前缀），保证从下标 0 开始的区间被正确统计。
参考实现
查看参考实现Python · 建议先自行作答
def subarraySum(nums, k):
# count 存每个前缀和出现次数；0 出现一次代表空前缀
count = {0: 1}
prefix = ans = 0
for x in nums:
prefix += x
ans += count.get(prefix - k, 0)
count[prefix] = count.get(prefix, 0) + 1
return ans