和为K的子数组

七崽爱吃小饼干2026/01/27阅读 0专栏算法合集

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

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

示例 1：

codeType

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

示例 2：

codeType

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

提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

解法

要注意的是，k和nums[i]都有可能是负数

解法一：暴力枚举

var subarraySum = function(nums, k) {
    let count = 0;
    for (let start = 0; start < nums.length; ++start) {
        let sum = 0;
        for (let end = start; end >= 0; --end) {
            sum += nums[end];
            if (sum == k) {
                count++;
            }
        }
    }
    return count;
};

解法二：前缀和

function subarraySum(nums: number[], k: number): number {
    // 因为nums[i]和k都可能是负数，所以不可以用滑动窗口解决
    // 计算前缀和，通过前缀和，可以任意O(1)内得到[i,j]的元素和 = preSum[j] - preSum[i - 1]
    // 防止越界，preSum[-1] = 0
    /**
    preSum[0] = n₀
    preSum[1] = n₀ + n₁
    preSum[2] = n₀ + n₁ + n₂
    ...
    preSum[i] = n₀ + n₁ + ... + nᵢ
     */
    const n = nums.length
    const PreSum = new Array(n).fill(0)
    let count = 0
    for(let i = 0; i < n; i++){
        count += nums[i]
        PreSum[i] = count
    }
    let res = 0
    for(let i = 0; i < n; i++){
        for(let j = i; j < n; j++){
            let sum = PreSum[j] - (i === 0 ? 0 : PreSum[i - 1])
            if(sum === k) res++
        }
    }
    return res
};

解法三：哈希表+前缀和

function subarraySum(nums: number[], k: number): number {
    // 哈希表：记录前缀和及其出现的次数（优化内层循环，时间复杂度O(n)）
    const preSumCountMap = new Map<number, number>();
    // 初始化：前缀和为0的情况出现1次（对应preSum[-1] = 0，解决i=0的边界问题）
    preSumCountMap.set(0, 1);
    
    let currentPreSum = 0; // 动态累加当前前缀和（替代显式的PreSum数组）
    let result = 0; // 符合条件的子数组数量

    for (const num of nums) {
        // 1. 动态计算当前前缀和（对应原代码的PreSum[j]）
        currentPreSum += num;

        // 2. 寻找目标前缀和：target = currentPreSum - k（对应原代码的PreSum[i-1]）
        const targetPreSum = currentPreSum - k;

        // 3. 若目标前缀和存在，累加其出现次数到结果中（替代内层循环枚举i）
        if (preSumCountMap.has(targetPreSum)) {
            result += preSumCountMap.get(targetPreSum)!;
        }

        // 4. 更新哈希表：当前前缀和出现的次数+1
        preSumCountMap.set(
            currentPreSum,
            (preSumCountMap.get(currentPreSum) || 0) + 1
        );
    }

    return result;
}