力扣 560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
方案一：套用优美子数组 中前缀和的方案。
func subarraySum(nums []int, k int) (ans int) {
// 定义无序映射，key 为前缀和值，val 为能达到这个前缀和的子数组个数
mp := make(map[int]int, len(nums))
// 前缀和为 0 表示什么数字都不选，这种情况的子数组有且只有一个，即空数组
mp[0] = 1
// 定义前缀和
preSum := 0
for _, num := range nums {
// 计算前缀和
preSum += num
// curr presum - prev presum == k ==> curr presum - k = pre presum
// 这里的 previous presum 就是子数组个数
ans += mp[preSum - k]
// 记录当前前缀和的情况
mp[preSum]++
}
return
}
- 时间复杂度：O(n)，因为需要遍历所有数字才能计算出结果，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)， 因为需要一个容量为 n 的无序映射保存前缀和信息，所以空间复杂度为 O(n)。