数组前缀和

• 概述

前缀和是预处理数组的一种技巧，常用来计算子数组的和。
定义前缀和数组。
这种定义方式不包含0，前缀数组的维度和原数组维度相同。
区间的和为。当时，取。
区间的和为当时，取。
在Python中，可以用如下代码得到以此方式定义的前缀和：

nums = [1, 2, 3]
from itertools import accumulate
pre = list(accumulate(nums))

若定义前缀和数组为。
则区间的和为。区间的和为。
在Python中，可以用如下代码得到以此方式定义的前缀和：

nums = [1, 2, 3]
pre = [0] * (len(nums) + 1)
for i in range(len(nums)):
    pre[i+1] = pre[i] + nums[i]

• 利用前缀和求解子数组和问题

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
来源：Leetcode560题
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/
参考解答：
超时解答：复杂度
Python语言比较慢，其他语言复杂度为的解法可以通过。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        pre = list(accumulate(nums))
        ans = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if pre[j] - (pre[i-1] if i != 0 else 0) == k:
                    ans += 1
        return ans

使用字典优化：复杂度

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        s = 0
        d = collections.defaultdict(int)
        ans = 0
        d[0] = 1
        for i in range(len(nums)):
            s += nums[i]  # s实际上就是前缀和，只不过没有写成数组的形式
            ans += d[s - k]
            d[s] += 1
        return ans