limanting 的个人博客

题目

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

我的答案

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    const sumMap = new Map([[0,1]]);
    let preSum = 0;
    let resCount = 0;
    for (let i = 0; i < nums.length; i++) {
        preSum += nums[i];
        if (sumMap.get(preSum - k)) {
            resCount += sumMap.get(preSum - k);
        }
        sumMap.set(preSum, sumMap.get(preSum) ? sumMap.get(preSum) + 1 : 1);
    }
    return resCount;

};

前缀和 + 哈希表

要取的是j～i个数，利用前缀和就需要求差，即P（i）-P（j）= k ，在计算第P（i）个时，前面P（j）已经是计算过的，所以求P（i）-k 找是否存在P（j）即可，为了防止有0 的出现，所以要计算每个P值出现过几次。

复杂度O（n）