001.和为 K 的子数组

• 560.和为 K 的子数组
  • 前缀和
  • 前缀和优化

和为 K 的子数组 - 前缀和

func subarraySum(nums []int, k int) int {
	res := 0
	n := len(nums)
	sum := make([]int, n + 1)
	sum[0] = 0
	for i, num := range nums {
		sum[i + 1] = sum[i] + num
	}
	for end := n; end > 0; end-- {
		for start := 0; start < end; start++ {
			if sum[end] - sum[start] == k {
				res++
			}
		}
	}
	return res
}

和为 K 的子数组 - 前缀和优化

func subarraySum(nums []int, k int) int {
	res := 0
	sum := 0
	prev := map[int]int{
		0: 1,
	}
	for _, num := range nums {
		sum += num
		if count, has := prev[sum - k]; has {
			res += count
		}
		prev[sum]++
	}
	return res
}