题目描述
给你一个整数数组 nums 和一个整数 k，请你统计并返回 该数组中和为 k 的子数组的个数。 子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
思路&js代码
1、枚举
var subarraySum = function (nums, k) {
let count = 0
for (let i = 0; i < nums.length; i++) {
let sum = 0
for (let j = i; j < nums.length; j++) {
sum += nums[j]
if (sum === k) count++
}
}
return count
};2、前缀和 + 哈希表
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;
};