和为K的子数组

题目描述
给定一个整数数组 nums 和一个整数 k，你需要计算数组中连续子数组的和等于 k 的子数组数量。
示例：
输入：nums = [1,1,1], k = 2
输出：2
解释：连续子数组 [1,1] 和 [1,1]（从不同索引开始）的和均为 2。
注意：子数组是连续的，且数组长度可能达到 2 * 10^4，因此需要高效算法。

解题过程
这个问题如果使用暴力法，枚举所有子数组并计算和，时间复杂度为 O(n^2)，在 n 较大时会超时。我们需要一种更高效的方法，这里使用前缀和配合哈希表来达到 O(n) 的时间复杂度。

步骤 1：理解前缀和
前缀和 prefix[i] 表示从数组开头到第 i 个元素（包含）的总和。例如，对于 nums = [1,2,3]，前缀和数组为 [1,3,6]。
如果我们想要计算子数组 nums[i..j] 的和，可以用 prefix[j] - prefix[i-1]（当 i>0 时）。也就是说，子数组的和可以通过两个前缀和的差得到。

步骤 2：问题转化
我们要找子数组和等于 k，即：
prefix[j] - prefix[i] = k
这里 i 和 j 是前缀和数组的索引（注意 i 是子数组开始的前一个位置）。
移项：prefix[i] = prefix[j] - k
所以，对于每个位置 j，我们只需要看之前有多少个位置 i 的前缀和等于 prefix[j] - k，那么以 j 结尾的子数组中，和等于 k 的数量就是这些 i 的个数。

步骤 3：使用哈希表记录前缀和出现次数
我们可以一边遍历数组，一边计算当前前缀和，同时用哈希表（字典）记录之前每个前缀和值出现的次数。

• 初始化哈希表 prefix_count，键是前缀和的值，值是该前缀和出现的次数。初始时，前缀和为 0 出现 1 次（表示一个元素都不取的情况）。
• 遍历数组，计算当前前缀和 curr_sum。
• 查找哈希表中键为 curr_sum - k 的值，这个值就是以当前位置结尾的、和为 k 的子数组数量，累加到结果中。
• 将当前前缀和 curr_sum 的出现次数在哈希表中加 1。

步骤 4：示例推演
以 nums = [1,1,1], k = 2 为例：

1. 初始：prefix_count = {0:1}，结果 count=0，curr_sum=0。
2. 索引 0：curr_sum = 0+1=1。curr_sum - k = 1-2 = -1，哈希表中没有 -1，所以加 0。更新哈希表：prefix_count = {0:1, 1:1}。
3. 索引 1：curr_sum = 1+1=2。curr_sum - k = 2-2=0，哈希表中 0 出现 1 次，所以 count += 1（对应子数组 nums[0..1]）。更新哈希表：prefix_count = {0:1, 1:1, 2:1}。
4. 索引 2：curr_sum = 2+1=3。curr_sum - k = 3-2=1，哈希表中 1 出现 1 次，所以 count += 1（对应子数组 nums[1..2]）。更新哈希表：prefix_count = {0:1, 1:1, 2:1, 3:1}。
   结果 count = 2。

步骤 5：考虑边界情况

• 数组为空：直接返回 0。
• k 可能为负数：方法依然有效，因为哈希表存储的是前缀和值。
• 前缀和可能很大，但哈希表能高效处理。

步骤 6：算法实现

def subarraySum(nums, k):
    from collections import defaultdict
    prefix_count = defaultdict(int)
    prefix_count[0] = 1  # 初始前缀和为0出现一次
    curr_sum = 0
    count = 0
    for num in nums:
        curr_sum += num
        if curr_sum - k in prefix_count:
            count += prefix_count[curr_sum - k]
        prefix_count[curr_sum] += 1
    return count

复杂度分析

• 时间复杂度：O(n)，遍历数组一次，哈希表操作平均 O(1)。
• 空间复杂度：O(n)，哈希表最多存储 n+1 个前缀和。

关键点总结
这道题的核心是利用前缀和将子数组和问题转化为两数之差问题，再通过哈希表记录历史前缀和的出现次数，从而在 O(1) 时间内查询到需要的数量。这种方法避免了双重循环，是典型的“空间换时间”策略，在涉及连续子数组和的问题中非常有用。