一、问题定义
给定整数数组 nums 和目标值 k，计算有多少个连续子数组的和恰好等于 k。
示例：
输入: nums = [1, 2, 3], k = 3
输出: 2
解释: [1,2] 和 [3] 两个子数组的和为3二、常见误区：为什么不能用滑动窗口？
⚠️ 关键陷阱：滑动窗口仅适用于非负数组。当数组包含负数或零时，窗口无法单调移动，会导致错误结果。
例如 nums = [1, -1, 1, 1], k = 2，滑动窗口会漏掉 [1, -1, 1, 1] 这个有效子数组。
三、正确解法：前缀和 + 哈希表
核心思路
- 前缀和定义：
prefixSum[i]= 从索引0到i的元素累加和 - 关键观察：若存在
prefixSum[j] - prefixSum[i] = k，则子数组[i+1...j]的和为k - 哈希表优化：边遍历边记录每个前缀和出现的次数，实现O(1)查询
算法步骤
def subarraySum(nums, k):
from collections import defaultdict
# 哈希表：前缀和 -> 出现次数
prefix_count = defaultdict(int)
prefix_count[0] = 1 # 初始化：空前缀和为0
current_sum = 0
result = 0
for num in nums:
current_sum += num
# 查找是否存在 prefix_sum = current_sum - k
if (current_sum - k) in prefix_count:
result += prefix_count[current_sum - k]
# 记录当前前缀和
prefix_count[current_sum] += 1
return result
💡 为什么初始化 prefix_count[0] = 1？
表示"从数组开头到当前位置的和恰好为k"的情况。例如
表示"从数组开头到当前位置的和恰好为k"的情况。例如
nums = [3], k = 3，需要这个初始值才能正确计数。
四、复杂度分析
- 时间复杂度：O(n)，单次遍历
- 空间复杂度：O(n)，哈希表存储前缀和
五、面试追问与应对
Q1: 能否优化空间到O(1)？
A: 对于"统计数量"的问题，无法优化。但如果只需判断"是否存在"，可以用集合代替哈希表。
Q2: 负数会影响算法吗？
A: 不影响前缀和方案，但会让滑动窗口完全失效。这正是前缀和方案的优势所在。
Q3: 为什么要记录前缀和的"出现次数"？
A: 因为多个不同的子数组可能有相同的前缀和差值。例如 [1, -1, 1], k=1，需要统计所有符合条件的组合。
六、扩展变体
- 最长子数组：找和为k的最长连续子数组
- 二维矩阵：扩展到矩阵中的子矩阵和问题
- 乘积版本：子数组乘积等于k（需要处理0和负数）