560 和为 K 的子数组

题目链接：560. 和为 K 的子数组

核心思考

1. 为什么滑动窗口失效？

在处理子数组求和问题时，滑动窗口（双指针）通常是首选。但本题的数据范围指出 $nums[i]$ 包含负数（$-1000 \leq nums[i] \leq 1000$）。
这意味着区间和不再具备单调性：窗口右移时和可能减小，收缩左边界时和可能增加。单调性的丧失导致滑动窗口的收敛条件无法确立，无法通过双指针在 $O(N)$ 时间内解决。

2. 前缀和与哈希表优化

为了将求解子数组和的复杂度从 $O(N)$ 降至 $O(1)$，我们引入前缀和 (Prefix Sum) 概念。
任意连续子数组 $nums[i \dots j]$ 的和可以表示为：
$$preSum[j] - preSum[i-1] = k$$

进一步变形公式，查找符合条件的子数组等价于查找历史状态：
$$preSum[i-1] = preSum[j] - k$$

我们在遍历索引 $j$ 的过程中，通过 Hash Map 维护 <历史前缀和, 出现频次> 的映射。这样，原本需要 $O(N)$ 回溯的操作被优化为 $O(1)$ 的状态检索，整体时间复杂度被控制在 $O(N)$。

代码实现

在实现时，我们需要预置边界条件 pre_sum_map[0] = 1。这是为了捕获那些从索引 0 开始且累加和恰好等于 k 的子数组（此时所需查询的目标补值为 0）。

import collections

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 维护 <前缀和 : 出现次数> 的映射
        pre_sum_map = collections.defaultdict(int)
        # 初始化边界：前缀和为 0 出现 1 次
        pre_sum_map[0] = 1
        
        curr_sum = 0
        count = 0
        
        for num in nums:
            curr_sum += num
            
            # 查找是否存在符合条件的历史状态 preSum[i-1] = curr_sum - k
            if (curr_sum - k) in pre_sum_map:
                count += pre_sum_map[curr_sum - k]
            
            # 记录当前前缀和频次
            pre_sum_map[curr_sum] += 1
            
        return count

复杂度分析

• 时间复杂度：$O(N)$
  只需对数组进行一次线性扫描。在循环内部，哈希表的插入与查询操作均为 $O(1)$。
• 空间复杂度：$O(N)$
  在最坏情况下（前缀和互不相同），哈希表最多存储 $N+1$ 个键值对。

---

关键点总结：

1. 单调性：负数的存在排除了滑动窗口方案。
2. 状态转换：将“寻找区间”转化为“查找历史前缀和状态”。
3. 哨兵节点：pre_sum_map[0] = 1 确保了边界逻辑的完备性。