碰到了一道题，用到了前缀和，记录一下

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1
2
输入：nums = [1,1,1], k = 2
输出：2

示例 2：

1
2
输入：nums = [1,2,3], k = 3
输出：2

我的超级烂写法(AC)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
}
  • 前缀树

请务必记住下面这个定义：

我们使用一个叫做“前缀和”的概念。对于数组中的任何位置 j，前缀和 pre[j] 是数组中从第一个元素到第 j 个元素的总和。这意味着如果你想知道从元素 i+1 到 j 的子数组的和，你可以用 pre[j] - pre[i] 来计算。

因此，在我的代码上改成前缀树版本的，根本不行，所以我的一开始的思路就是错的

1
2
3
4
5
6
7
8
9
10
11
12
13
func subarraySum(nums []int, k int) int {
    count := 0
    for start := 0; start < len(nums); start++ {
        sum := 0
        for end := start; end >= 0; end-- {
            sum += nums[end]
            if sum == k {
                count++
            }
        }
    }
    return count
}

把里面一层的遍历改成 从尾巴到头部 遍历的一个方式

这样子可以实现前缀树的性质：从第一个到第i个的和

所以我们可以使用 哈希表 + 前缀树 来优化他

map[int]int{num,count} 来表示连续和的出现的次数

然后我们使用 preSum - k 来表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func subarraySum(nums []int, k int) int {
	preArr := map[int]int{0: 1}
	preSum := 0 
	ans := 0

	for i := 0; i < len(nums); i++ {
		preSum += nums[i]
		if pre , ok := preArr[preSum - k]; ok{
			ans += pre
		}
		preArr[preSum]++
		
	}
	
	return ans
}

  1. preSum 记录的是从头到第i个的和

  2. pre , ok := preArr[preSum - k] 这个就表示 arr[j] - arr[i] = arr[ i+1 ~j ] 的连续和，那么反观我们写的算式：

    preSum = arr[j]

    k=arr[i]

    那么pre 的存在个数就是 连续个数，非常巧妙