560. 和为 K 的子数组 (Medium)
专题归类： 数组 · 哈希表 LeetCode 链接： https://leetcode.cn/problems/subarray-sum-equals-k/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 nums 和一个整数 k，请你统计并返回 该数组中和为 k 的连续子数组的个数。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
解释：[1,1] 出现两次（索引 0~1 和 1~2）
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
解释：[1,2] 和 [3] 两个子数组和为 3
补充说明：
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7- 子数组是连续的、非空的元素序列
题目详细分析
数据范围分析：
- 数组长度最大 2×10^4，O(n^2) 的枚举法（约 4 亿次操作）会超时，必须 O(n) 或 O(n log n) 解决。
- 元素值可正可负可为 0，这意味着不能用双指针（滑动窗口），因为双指针要求单调性，而负数会导致和不是单调的。
- k 的范围很大（±10^7），但哈希表存的是前缀和的值，与 k 大小无关。
输入输出特征：
- 输入是整数数组和整数 k，输出是整数（子数组个数）。
- 子数组必须是连续的，不是子序列（子序列可以跳着选）。
- 只统计个数，不需要返回具体的子数组。
边界条件：
- 整个数组的和恰好等于 k
- k = 0 时，需要统计所有和为 0 的子数组
- 数组中包含负数，可能导致前缀和先增后减，同一个前缀和值可能出现多次
- 空子数组不算（题目没说，但按常规子数组定义，非空才算）
隐藏条件：
- 元素有负数意味着滑动窗口不可行，这直接决定了只能用前缀和+哈希表。
- 前缀和可能非常大（n × max(nums) = 2×10^4 × 1000 = 2×10^7），仍在 32 位整数范围内。
小白版直白理解
想象你在逛一条商业街，街边有一排店铺，每个店铺的利润不同（有的赚钱是正数，有的亏钱是负数）。
你想知道：有多少段连续店铺的总利润恰好是 k 元？
方法一（暴力，太慢）： 列举所有可能的连续店铺组合——从第 i 家到第 j 家，挨个算总利润，看是不是 k。这就好比把每条可能的路线都走一遍，非常累。
方法二（聪明法）： 你带了一个小本本，每走过一家店就记下从街头到当前店的总利润。比如走到第 5 家时总利润是 100，而你想要利润为 20 的连续段，那你就翻小本本看有没有哪次记的总利润是 80（因为 100 - 80 = 20）。如果有，就说明从那家店到第 5 家这段的利润正好是 20。
这个小本本不仅记总利润是多少，还记这个总利润出现过几次——因为同样的总利润可能出现多次，意味着有多个不同的起点都能得到目标利润段。
解题思路
思路一：前缀和 + 哈希表（推荐）
核心洞察： 子数组 nums[j..i] 的和 = prefix[i] - prefix[j-1]。要求这个和等于 k，即 prefix[j-1] = prefix[i] - k。所以当我们在位置 i 时，只需要知道有多少个前缀和等于 prefix[i] - k。
为什么用哈希表： 我们需要快速查询某个前缀和的出现次数，哈希表 O(1) 查询正合适。
为什么初始化 {0: 1}： 前缀和为 0 对应「空数组」。如果一个子数组从头开始（索引 0 到 i）的和就是 k，那么我们需要 prefix[-1] = 0 来匹配，所以初始化 0 出现 1 次。
def subarraySum(nums, k):
# 哈希表记录：前缀和 -> 出现次数
prefix = {0: 1}
cur_sum = 0 # 当前前缀和
count = 0 # 满足条件的子数组个数
for num in nums:
cur_sum += num # 更新前缀和
# 如果存在 cur_sum - k，说明有子数组的和为 k
if cur_sum - k in prefix:
count += prefix[cur_sum - k]
# 将当前前缀和存入哈希表
prefix[cur_sum] = prefix.get(cur_sum, 0) + 1
return count复杂度： O(n) 时间，O(n) 空间。
思路二：暴力枚举（不推荐，用于理解）
枚举所有起点和终点，计算每个子数组的和。O(n^2) 时间，大数据会超时。
def subarraySum_bruteforce(nums, k):
count = 0
n = len(nums)
for i in range(n):
cur_sum = 0
for j in range(i, n):
cur_sum += nums[j]
if cur_sum == k:
count += 1
return count思路三：前缀和数组 + 哈希表（理解过渡版）
先完整计算前缀和数组，再遍历。和思路一本质相同，但多了一次遍历和 O(n) 额外空间存前缀和数组。
def subarraySum_prefixArray(nums, k):
n = len(nums)
prefix = [0] * (n + 1) # prefix[i] 表示前 i 个元素的和
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
count = 0
hash_map = {}
for i in range(n + 1):
if prefix[i] - k in hash_map:
count += hash_map[prefix[i] - k]
hash_map[prefix[i]] = hash_map.get(prefix[i], 0) + 1
return count易错点
- 初始化
{0: 1}遗漏：忘记初始化会导致从开头到某位置的子数组（和为 k）被漏统计。 - 更新顺序：必须先查
cur_sum - k，再将当前cur_sum存入哈希表。如果先存再查，当 k=0 时每个位置都会把自己算进去（把空子数组也算上了）。 - 负数处理：因为有负数，前缀和可能重复出现多次，哈希表要记录次数（计数累加），而不是简单用集合。
- 整型溢出：Python 不用担心，但其他语言需要考虑前缀和是否超过 int 范围。
- 连续子数组 vs 子序列：题目要求连续，不要用子序列的思路去解。
框架提炼
前缀和 + 哈希表 通用模板：
def subarraySum(nums, k):
# Step 1: 初始化哈希表，记录前缀和出现次数
# 初始 {0: 1} 表示前缀和为 0 出现了 1 次（空数组）
prefix_count = {0: 1}
cur_sum = 0
result = 0
# Step 2: 一次遍历
for num in nums:
cur_sum += num # 更新当前前缀和
# Step 3: 查哈希表 — 找有多少个前缀和等于 cur_sum - k
# 这些前缀和对应的位置到当前位置的子数组就是答案
target = cur_sum - k
if target in prefix_count:
result += prefix_count[target]
# Step 4: 将当前前缀和加入哈希表
prefix_count[cur_sum] = prefix_count.get(cur_sum, 0) + 1
return result适用场景扩展： 这个模板可以解决一类问题——统计满足某种条件的连续子数组个数。关键在于：
- 找到合适的「前缀值」定义（和、积、异或和等）
- 写出条件等式：当前前缀值 - 目标 = 历史前缀值
- 用哈希表快速查找历史前缀值
类似问题：974-和可被K整除的子数组（条件变为 cur_sum % k）、437-路径总和 III（树上前缀和）。
关联题目
- 1-两数之和 — 本题是两数之”和”在连续子数组上的推广：两数之和是在数组中找两个数 a+b=k，本题是在前缀和中找两个前缀和之差等于 k。
- 437-路径总和 III — 完全一样的思路，只是从一维数组变成了二叉树，前缀和在树上就是「从根到当前节点的路径和」。
- 974-和可被K整除的子数组 — 前缀和 + 哈希表的同系列题目，条件从
cur_sum - k变为cur_sum % k。 - 525-连续数组 — 将 0/1 转为 ±1，再用前缀和+哈希表找和为 0 的最长连续子数组。