NOTES · 学习笔记
和为 K 的子数组
题目
我们拿示例 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 //得出结果
}