560.和为k的子数组

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

示例 1：

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

示例 2：

输入：nums = [1,2,3], k = 3
输出：2
方法一：枚举
时间复杂度：O(n2)
空间复杂度：O(1)

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} k
 4  * @return {number}
 5  */
 6 var subarraySum = function (nums, k) {
 7     let count = 0;
 8     for (let start = 0; start < nums.length; ++start) {
 9         let sum = 0;
10         for (let end = start; end >= 0; --end) {
11             sum += nums[end];
12             if (sum == k) {
13                 count++;
14             }
15         }
16     }
17     return count;
18 };

方法二：前缀和+哈希表优化
时间复杂度：O(n)
空间复杂度：O(n)

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} k
 4  * @return {number}
 5  */
 6 var subarraySum = function(nums, k) {
 7     const mp = new Map();
 8     mp.set(0, 1);
 9     let count = 0,
10         pre = 0;
11     for (const x of nums) {
12         pre += x;
13         if (mp.has(pre - k)) {
14             count += mp.get(pre - k);
15         }
16         if (mp.has(pre)) {
17             mp.set(pre, mp.get(pre) + 1)
18         } else {
19             mp.set(pre, 1);
20         }
21     }
22     return count;
23 }