560. Subarray Sum Equals K

[Tcdian]

560. Subarray Sum Equals K

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

Example

Input:nums = [1,1,1], k = 2
Output: 2

Note

• 数组的长度为 [1, 20,000]。
• 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const cache = new Map();
    let prefixSum = 0;
    let result = 0;
    cache.set(0, 1);
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i]
        if (cache.has(prefixSum - k)) {
            result += cache.get(prefixSum - k);
        }
        cache.set(prefixSum, (cache.get(prefixSum) || 0) + 1)
    }
    return result;
};