我来给你讲解 LeetCode 第 560 题：和为 K 的子数组。

题目描述

给定一个整数数组 nums 和一个整数 k，你需要找到该数组中和为 k 的连续子数组的个数。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
解释：[1,1] 和 [1,1]（注意有两个位置不同的子数组）

示例 2：

输入：nums = [1,2,3], k = 3
输出：2
解释：[1,2] 和 [3]

解题思路循序渐进

第一步：暴力解法（理解问题本质）

最直接的思路是枚举所有可能的子数组：

• 对于每个起始位置 i，计算从 i 到各个结束位置 j 的子数组和
• 检查是否等于 k

def subarraySum(nums, k):
    count = 0
    n = len(nums)
    
    for i in range(n):          # 起始位置
        current_sum = 0
        for j in range(i, n):   # 结束位置
            current_sum += nums[j]
            if current_sum == k:
                count += 1
    
    return count

时间复杂度： O(n²) - 对于每个起始位置，都要遍历到数组末尾
空间复杂度： O(1)

这种方法虽然直观，但在大数据量时效率太低。

第二步：优化思路 - 前缀和的概念

我们可以引入前缀和的概念来优化：

• 定义 prefix[i] 表示从 nums[0] 到 nums[i] 的和
• 那么子数组 [i, j] 的和 = prefix[j] - prefix[i-1]

具体来说：

• 如果我们想要子数组 [i, j] 的和为 k，那么：
  prefix[j] - prefix[i-1] = k
• 转换一下：prefix[i-1] = prefix[j] - k

这意味着：对于每个位置 j，我们需要找前面有多少个位置 i，使得 prefix[i] = prefix[j] - k

第三步：哈希表优化

我们可以用哈希表来记录每个前缀和出现的次数，这样可以在 O(1) 时间内查询：

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    prefix_count = {0: 1}  # 前缀和为0出现1次（空子数组）
    
    for num in nums:
        prefix_sum += num
        
        # 检查是否存在 prefix[i] = prefix_sum - k
        if (prefix_sum - k) in prefix_count:
            count += prefix_count[prefix_sum - k]
        
        # 更新当前前缀和的出现次数
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
    
    return count

第四步：详细示例演示

以 nums = [1,1,1], k = 2 为例：

遍历过程：

1. i=0, num=1: prefix_sum=1

   • 需要找 prefix_sum-k = 1-2 = -1，不存在
   • prefix_count = {0:1, 1:1}

2. i=1, num=1: prefix_sum=2

   • 需要找 2-2=0，存在，count += prefix_count[0] = 1
   • prefix_count = {0:1, 1:1, 2:1}

3. i=2, num=1: prefix_sum=3

   • 需要找 3-2=1，存在，count += prefix_count[1] = 1
   • prefix_count = {0:1, 1:1, 2:1, 3:1}

最终结果：count = 2

第五步：关键点解释

1. 为什么需要 prefix_count = {0: 1}？

   • 这是为了处理从数组开头开始的子数组
   • 比如子数组 [0, j] 的和就是 prefix[j] - prefix[-1]，而 prefix[-1] 应该是 0

2. 为什么是 prefix_sum - k？

   • 因为我们要找的是：prefix[j] - prefix[i] = k
   • 所以 prefix[i] = prefix[j] - k

3. 时间复杂度： O(n) - 只需遍历一次数组

4. 空间复杂度： O(n) - 哈希表存储前缀和

第六步：边界情况考虑

• 数组为空：返回 0
• k=0：需要特殊处理（但上述算法天然支持）
• 包含负数：算法仍然有效
• 多个相同前缀和：哈希表记录次数，都能正确统计

这种前缀和+哈希表的方法是解决"子数组和为k"类问题的标准解法，理解了这个思路，类似问题都能迎刃而解。