第三章：前缀和技巧

labuladong 前缀和技巧

560. 和为K的子数组

方法1：前缀和 (暴力超时)

保存一个数组的前缀和，然后利用差分法得出任意区间段的和

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
      cnt, n =  0, len(nums)
      pre = [0] * (n + 1)
      for i in range(1, n + 1):
          pre[i] = pre[i - 1] + nums[i - 1]
      for i in range(1, n + 1):
          for j in range(i, n + 1):
              if (pre[j] - pre[i - 1] == k): cnt += 1
      return cnt

方法2：改进版的前缀和，维护更新hashmap

• 维护一个hashmap，hashmap的key 为累加值 acc，value 为累加值 acc 出现的次数。
• 遍历数组，然后不断更新 acc 和 hashmap，如果 acc 等于 k，那么很明显应该+1. 如果 hashmap[acc - k] 存在，我们就把它加到结果中去即可。

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        from collections import defaultdict
        record=defaultdict(int)
        res=0
        presum=0 # 记录前缀和
        for i in nums:
            presum+=i
            if presum ==k: # 如果当前的前缀和为1，则计数+1
                res+=1
            if presum-k in record: # presum-k已存在，则把record[presum-k]加到结果中
                res+=record[presum-k]
            record[presum]+=1
        return res