和为K的子数组

1. 题目描述

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

2. 思路

1. 思路一
   • 暴力
   • 两层for循环计算和
2. 前缀和

3. 实现

3.1. 暴力

package main

func subarraySum(nums []int, k int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum == k {
				count++
			}
		}
	}
	
	return count
}

3.2. 前缀和

func subarraySum(nums []int, k int) int {
	// key是前缀和，value是前缀和的个数
	preSumCount := make(map[int]int, 0)
	preSumCount[0] = 1
	preSum := 0
	count := 0
	for _, num := range nums {
		preSum += num
		count += preSumCount[preSum-k]
		preSumCount[preSum] += 1
	}
	return count
}

4. 参考

• 560. 和为K的子数组 - 力扣（LeetCode）
• 暴力解法、前缀和、前缀和优化（Java） - 和为 K 的子数组 - 力扣（LeetCode）