和为 K 的子数组

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：前缀和、哈希表

给你一个整数数组 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] 是和为 3 的子数组。

---

2. 解题思路拆解

为什么不用滑动窗口？

这道题虽然是求“子数组”，但由于数组中可能包含负数，子数组的和并不是单调递增的。这意味着我们不能简单地用滑动窗口（双指针）来解决。

方法：前缀和 + 哈希表优化

1. 前缀和定义：pre[i] 表示 nums[0]...nums[i] 的和。
2. 子数组和的转换：
   • 子数组 nums[j...i] 的和可以表示为 pre[i] - pre[j-1]。
   • 题目要求找到和为 k 的子数组，即寻找满足 pre[i] - pre[j-1] == k 的 (i, j) 对数。
3. 公式变形：
   • 移项得到：pre[j-1] == pre[i] - k。
   • 这就把问题转化为了：遍历到位置 i 时，在它前面（0 到 i-1）有多少个前缀和等于 pre[i] - k。
4. 哈希表优化：
   • 我们可以用一个哈希表 map 记录前缀和出现的次数：key 是前缀和的值，value 是出现的次数。
   • 在遍历过程中，一边计算当前的 pre，一边去 map 中找 pre - k 出现的次数，累加到答案中。
   • 初始化：map.set(0, 1)。这代表“前缀和为 0 出现了一次”。这是为了处理从下标 0 开始的子数组（即 pre[i] == k 的情况，此时 pre[i] - k == 0）。

---

3. 代码实现

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    // map 存储前缀和出现的次数
    // key: 前缀和, value: 次数
    const map = new Map();
    // 初始化：前缀和为 0 出现 1 次（处理子数组从头开始的情况）
    map.set(0, 1);
    
    let count = 0;
    let pre = 0;
    
    for (const num of nums) {
        pre += num;
        
        // 查找是否存在 pre - k 的前缀和
        if (map.has(pre - k)) {
            count += map.get(pre - k);
        }
        
        // 更新当前前缀和的计数
        map.set(pre, (map.get(pre) || 0) + 1);
    }
    
    return count;
};

代码执行演示

输入 nums = [1, 2, 3], k = 3

1. 初始化：map = {0: 1}, count = 0, pre = 0
2. 遍历 num = 1：
   • pre = 1
   • pre - k = 1 - 3 = -2。Map 中无 -2。
   • Map 更新：{0: 1, 1: 1}
3. 遍历 num = 2：
   • pre = 1 + 2 = 3
   • pre - k = 3 - 3 = 0。Map 中有 0，次数为 1。
   • count += 1 -> count = 1。 (对应子数组 [1, 2])
   • Map 更新：{0: 1, 1: 1, 3: 1}
4. 遍历 num = 3：
   • pre = 3 + 3 = 6
   • pre - k = 6 - 3 = 3。Map 中有 3，次数为 1。
   • count += 1 -> count = 2。 (对应子数组 [3])
   • Map 更新：{0: 1, 1: 1, 3: 1, 6: 1}
5. 结束：返回 2。

---

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。只需要遍历一次数组，哈希表的操作是 $O(1)$ 的。
空间复杂度	$O(n)$。最坏情况下，所有前缀和都不同，哈希表需要存储 $n$ 个键值对。