前往此题

前缀和

如果我们要得到[i, j]区间的总和我们可以通过[0,j] - [0,i]（其中j >= i）来获得。借助这个公式我们可以先创建一个预处理数组pre，pre中存储了[0, i)中的和。即pre[i] = sum([0,i])。

代码

N = len(nums)
pre = [0] * (N + 1)
for i in range(N):
    pre[i] = sum
    sum += nums[i]

因为题中我们需要不断的去查找数组中各种和为k的连续子数组，最直观的是用双重循环来解决

count = 0
for i in range(N + 1):
    for j in range(i+1, N+1):
        if pre[j] - pre[i] == k:
            count += 1
return count

但是这样做显然时间复杂度过高，达到了O(N^2)。因为中间有过多的重复计算，接下来我们要想办法对其进行优化。

前缀和 + 哈希表

将计算过的和存储到哈希表中来减少重复运算。

• sums : 前缀和pre[j]
• res: 符合 pre[j] - k == pre[i]的个数

前面我们知道pre[j] = pre[i] + nums[i]

既：

• pre[j] - pre[i] = nums[i]
• pre[j] - pre[i] = [i..j]
• pre[j] - pre[i] = [i..j] = k
• pre[j] - k = pre[i]

这里我们只需要知道pre[j] - k之后正巧有遇到之前的前缀和那么该位置pre[i..j]就是我们要找的和为k的连续子数组，接着我们将pre[j] - k存入哈希表中进行统计即可：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hs = {}
        hs[0] = 1

        sums, res = 0, 0

        for n in nums:
            sums += n     ## 前缀和：pre[j]
            if sums - k in hs:  ## sums - k 代表 [0..i]的和
                res += hs[sums-k]
            if sums in hs:
                hs[sums] = hs[sums] + 1
            else:
                hs[sums] = 1
        return res