前端力扣刷题 | 4：hot100之 子串

560. 和为K的子数组

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

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

示例：

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

法一：暴力法

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

法二：前缀和+哈希表

• 使用前缀和存储累计值，利用 currentSum - k 快速找到满足条件的子数组。

function subarraySum(nums, k) {
    // 初始化前缀和计数器
    const prefixSumCount = new Map();
    prefixSumCount.set(0, 1); // 初始前缀和为0，出现次数为1
    let currentSum = 0;
    let result = 0;

    for (const num of nums) {
        // 更新当前前缀和
        currentSum += num;

        // 检查是否存在满足条件的前缀和
        if (prefixSumCount.has(currentSum - k)) {
            result += prefixSumCount.get(currentSum - k);
        }

        // 更新前缀和计数器
        prefixSumCount.set(
            currentSum,
            (prefixSumCount.get(currentSum) || 0) + 1
        );
    }
    return result;
}