560. 和为 K 的子数组

[webVueBlog]

560. 和为 K 的子数组

Description

Difficulty: 中等

Related Topics: 数组, 哈希表, 前缀和

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 10⁴
• -1000 <= nums[i] <= 1000
• -10⁷ <= k <= 10⁷

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

// 前缀和 + 哈希表优化
var subarraySum = function(nums, k) {
    const mp = new Map();
    mp.set(0, 1);
    let count = 0, pre = 0;
    for (const x of nums) {
        pre += x;
        if (mp.has(pre - k)) {
            count += mp.get(pre - k);
        }
        if (mp.has(pre)) {
            mp.set(pre, mp.get(pre) + 1);
        } else {
            mp.set(pre, 1);
        }
    }
    return count;
};