LeetCode-560.和为 K 的子数组

哈希表#

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

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

示例 1：

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

示例 2：

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

1.解法

思路：1.负数破坏了单调性，所以不能用滑动窗口

2.前缀和 + 哈希表 | k = 两个前缀和的差

3.参考1. 两数之和

1
func subarraySum(nums []int, k int) int {
2
    sum := 0
3
    m := make(map[int]int)
4
    m[0] = 1
5
    res := 0
6

7
    for i := 0; i < len(nums); i++ {
8
        sum += nums[i]
9
        need := sum - k
10
        if j, ok := m[need]; ok {
11
            res += j
12
        }
13
        m[sum]++
14
    }
15
    return res
16
}