前缀和

假设有一个从零开始的数组nums，长度为n，我们可以通过计算前缀和数组prefixSum来快速计算任意区间[i,j]的和。

前缀和数组prefixSum的定义如下：
prefixSum[i] = nums[0] + nums[1] + … + nums[i-1]
即prefixSum[i] = prefixSum[i-1] + nums[i-1]
其中prefixSum[0] = 0

有了上面的定义，我们可以快速计算任意区间[i,j]的和：
sum[i,j] = prefixSum[j+1] - prefixSum[i]

例题

leetcode 560. 和为K的子数组
给定一个整数数组和一个整数k，找到该数组中和为k的连续子数组的个数。

思路： 由于是连续非空子数组，我们可以使用前缀和数组来计算任意区间的和，然后通过判断prefixSum[j+1]-prefixSum[i]==k来判断是否存在和为k的子数组，由于题目限制时间，可以通过哈希表来记录之前前缀和出现的次数，从而加快计算 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def subarraySum(self, nums: List[int], k: int) -> int:
    # 初始值为0
    ans = 0
    # 哈希表记录 （前缀和，出现次数）
    cnt = defaultdict(int)
    # 前缀和，初始化为0
    s = 0
    # 定义前缀和为0的情况，出现一次
    cnt[0] = 1
    # 遍历数组
    for num in nums:
        # 计算前缀和
        s += num
        # 如果存在前缀和为s-k的情况，且当前前缀和为s，也就是存在一个区间[i,j]，使得sum[i,j] = k，那么就统计上这个区间
        ans += cnt[s - k]
        # 更新前缀和为s的情况
        cnt[s] += 1
    # 返回结果
    return ans