NOTES · 学习笔记

和为 K 的子数组

LeetCode子串 · 中等约 3 分钟

题目

我们拿示例 2 来讲解思路。

数组中包含 [1,2,3],k=3,求和为 3 的子数组个数。

因为子数组必须是连续的,所以我们可以把所有连续的子数组列出来:

[1] → 不符合
[1,2] → 1+2=3,符合,次数+1
[1,2,3] → 不符合
[2] → 不符合
[2,3] → 不符合
[3] → 3=3,符合,次数+1

所以最后次数为 2,返回 2。

但是如果数组很长,一个一个子数组去算会很慢,所以我们才用“前缀和 + 哈希表”来优化。

我们先定义一个 sum,表示当前前缀和。

比如 [1,2,3]:

1 → sum=1
1+2 → sum=3
1+2+3 → sum=6

我们要求子数组的和等于 k。

如果当前前缀和是 sum,那么我们只需要找:

之前的前缀和 = sum-k

因为:

当前前缀和 - 之前的前缀和 = 子数组的和。

所以我们创建一个 hashmap 保存之前出现过的前缀和次数。刚开始 prefix[0]=1,表示前缀和 0 出现过 1 次。

然后遍历数组:

sum += num
count := prefix[sum-k]
res += count
prefix[sum]++

这里的 prefix[sum-k] 就是在找之前有没有出现过我们需要的前缀和。

如果出现了几次,就说明有几个符合条件的子数组,所以把 count 加到答案 res 中。

最后返回 res。

func subarraySum(nums []int, k int) int {
    prefix := make(map[int]int) //定义一个hashmap用来保存前缀和出现的次数
    sum := 0 //定义一个sum用来保存当前前缀和
    res := 0 //定义一个结果,最后我们输出这个res
    prefix[0] = 1 //初始化前缀和,表示前缀和0出现过1次
    for _, num := range nums {
        //每拿到一个num,我们就要更新一次前缀和
        sum += num
        //我们要找之前出现过的前缀和,用当前前缀和减去k
        count := prefix[sum-k] //我们定义一个count,用来查找之前出现过的前缀和

        res += count //找到几个就更新几个

        prefix[sum]++ //保存当前前缀和
    }
    return res //得出结果
}