JS_LeetCode10：和为K的子数组

img10.和为 K 的子数组

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

子数组是数组中元素的连续非空序列。

前缀和

不要想着遍历了，遍历一定会超时的！ T T

我们的目标是什么？找出子串！

在数组中随机定位一个子串，假如它满足条件，即和为k。

image-20250517002955641

除了直观的看到它们三个加起来的和等于k，这时候注意观察，这个子串的值其实还可以由红串减去黄串，而红串和黄串都是从第一个元素到它们的终点元素，这称做前缀和。任意一个满足条件的子串都具有这样的性质！

保存每个数组元素的前缀和吧，这并不耗时，况且我们的目标需要利用这些前缀和。

？ 有了前缀和，然后呢

根据图上，我们列出一个表达式：prefixSum[j] - prefixSum[i] = k

那转换一下，prefixSum[j] - k = prefixSum[i] ，这就代表着，我们遍历数组的元素，当前元素减去k的值，去前面的元素的前缀和寻找，找到多少个就将其计入总结果！

哈希表

快速的找前缀和，使用哈希表保存！

陷阱

注意了，考虑特殊情况！假如元素自身就满足添加，即为k，它要寻找的是不是前缀和为0的有几个？但是我们的map中可能不存在！所以需要初始化map[0]+1，确保自身满足条件的情况也计算正常。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const start = nums[0]
    const map = {}
    map[0] = 1
    let prefixSum = 0
    let res = 0
    for (let i = 0; i<nums.length; i++){
        prefixSum += nums[i]
        if (prefixSum - k in map){
            res += map[prefixSum-k]
        }
        map[prefixSum] = (map[prefixSum] || 0) + 1
    }
    return res

};