算法题-16

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2

对于这道题如果我们一个一个试，我们也会试出来答案是2

[1] = 1 ❌
[1,1] = 2 ✅
[1,1,1] = 3 ❌
[1] = 1 ❌
[1,1] = 2 ✅
[1] = 1 ❌

但是我们在试的是够的一个关键问题是从某个位置j到i的连续和，nums[j] + … + nums[i]。

假如我们一直往右边加，我们会发现nums = [1,1,1]，这个就是前缀和

看这个表，如果我们想知道有没有一段子数组和=2，我们发下，当我们在2位置的时候，前面有一个时刻的和是1，那么3-1=2，说明中间的那段=2，这样我们就找到了一个子数组

时间线：

0 —- 1 —- 2 —- 3
     ↑         ↑
   旧位置     现在

所以整体唯一的思想就是，不断地询问以前有没有一个“旧的累计和”，让：当前和 – 旧和 = k，也就是，旧和 = 当前和 – k

所以代码的思路是：
初始化map = { 0:1 }sum = 0，count = 0
为什么有 0？表示：还没开始时，和就是 0。
第一步：遇到 1，sum = 1，我们找：sum – k = 1 – 2 = -1，map 里没有，记录：map = {0:1, 1:1}
第二步：遇到 1，sum = 2，找：2 – 2 = 0，map 里有，说明：从开头到这里 = 2，count++，count = 1，记录：map = {0:1,1:1,2:1}
第三步：遇到 1，sum = 3，找：3 – 2 = 1，map 里有 ，说明：中间一段 = 2，count++，count = 2
最终答案2

function subarraySum(nums, k) {
const map = new Map();
map.set(0, 1);

let sum = 0;
let count = 0;

for (let num of nums) {
sum += num;

// 找过去的某个和
if (map.has(sum – k)) {
count += map.get(sum – k);
}

// 记录现在
map.set(sum, (map.get(sum) || 0) + 1);
}

return count;
}