560\. 和为 K 的子数组
# 560. 和为 K 的子数组 (opens new window)
# Description
Difficulty: 中等
Related Topics: 数组 (opens new window), 哈希表 (opens new window), 前缀和 (opens new window)
给你一个整数数组 nums
和一个整数 k
,请你统计并返回 _该数组中和为 k
的连续子数组的个数 _。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
1
2
2
示例 2:
输入:nums = [1,2,3], k = 3
输出:2
1
2
2
提示:
- 1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
- -107 <= k <= 107
# 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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25