2025-06-17

024-和为K的子数组（前缀和）

提示

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k* **的子数组的个数 *。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

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

一步步详细解答：前缀和 + 哈希表方法

1. 问题理解

我们需要统计数组中连续子数组的和等于 k 的个数。例如：

nums = [1,1,1], k = 2 → 输出 2（因为 [1,1] 和 [1,1] 都满足）
nums = [1,2,3], k = 3 → 输出 2（因为 [1,2] 和 [3] 都满足）

2. 暴力解法（O(n²)）

最直观的方法是双重循环，计算所有可能的子数组的和：

var subarraySum = function(nums, k) {
    let count = 0;
    for (let start = 0; start < nums.length; start++) {
        let sum = 0;
        for (let end = start; end < nums.length; end++) {
            sum += nums[end]; // 计算从 start 到 end 的和
            if (sum === k) {
                count++;
            }
        }
    }
    return count;
};

缺点：当 nums 很大时，效率很低（比如 nums.length = 10^5 时，计算量会非常大）。

3. 优化解法：前缀和 + 哈希表（O(n)）

为了优化，我们引入**前缀和（Prefix Sum）**的概念。

什么是前缀和？

前缀和是指从数组开头到当前位置的所有元素的和。例如：

nums = [1, 2, 3] 的前缀和数组是 [0, 1, 3, 6]（初始 0 是为了方便计算）。

为什么用前缀和？

假设我们有一个子数组 nums[i..j]，它的和可以表示为：

sum(nums[i..j]) = prefixSum[j+1] - prefixSum[i]

如果我们希望 sum(nums[i..j]) = k，那么：

prefixSum[j+1] - prefixSum[i] = k
=> prefixSum[j+1] - k = prefixSum[i]

也就是说，**如果 prefixSum[j+1] - k 在之前的前缀和中出现过，就说明存在一个子数组的和等于 k**。

如何用哈希表优化？

我们可以用一个哈希表 map 存储前缀和出现的次数，这样可以在 O(1) 时间内查询 prefixSum[j+1] - k 是否出现过。

代码实现

var subarraySum = function(nums, k) {
    let count = 0;
    let sum = 0;
    const map = new Map();
    map.set(0, 1); // 初始状态，前缀和为 0 出现 1 次

    for (let i = 0; i < nums.length; i++) {
        sum += nums[i]; // 计算当前的前缀和
        if (map.has(sum - k)) { // 检查 sum - k 是否出现过
            count += map.get(sum - k); // 如果有，说明存在子数组和为 k
        }
        map.set(sum, (map.get(sum) || 0) + 1); // 更新当前前缀和的出现次数
    }
    return count;
};

示例解析

例子 1：nums = [1,1,1], k = 2

i	nums[i]	sum (prefixSum)	sum - k	map (sum → count)	count
-	-	0	-	{0:1}	0
0	1	1	1-2=-1	{0:1, 1:1}	0
1	1	2	2-2=0	{0:1, 1:1, 2:1}	1
2	1	3	3-2=1	{0:1, 1:1, 2:1, 3:1}	2

**最终 count = 2**，符合预期。

例子 2：nums = [1,2,3], k = 3

i	nums[i]	sum (prefixSum)	sum - k	map (sum → count)	count
-	-	0	-	{0:1}	0
0	1	1	1-3=-2	{0:1, 1:1}	0
1	2	3	3-3=0	{0:1, 1:1, 3:1}	1
2	3	6	6-3=3	{0:1, 1:1, 3:1, 6:1}	2