560.和为K的子数组

https://leetcode-cn.com/problems/subarray-sum-equals-k/

先计算前缀和，然后双指针i，j遍历，i从1~n，j从0~i-1，若有preSum[i] - preSum[j] == k，说明nums[j+1...i]的和为k

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        preSum = [0]*(n+1)
        for i in range(n):
            preSum[i+1] = preSum[i] + nums[i]
        count = 0	#计数器
        for i in range(1, n+1):
            for j in range(i):
                if preSum[i] - preSum[j] == k:
                    count +=1
        return count

上面方法超时

改进

preSum[i] - preSum[j] = k 变式为 preSum[j] = preSum[i] - k

因为i>j，所以preSum[i]一定先于preSum[j]计算出来，每次将求出的preSum[i]记录在map，若得到的preSum[j]存在于map，说明符合题意

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        map = {}  # key为前缀和，value为出现次数
        map[0] = 1
        preSum_i = 0
        count = 0
        for i in range(n):
            preSum_i += nums[i]
            preSum_j = preSum_i - k
            if preSum_j in map:     #看preSum[j]是否已被计算出来
                count += map[preSum_j]
            map[preSum_i] = map.get(preSum_i, 0) + 1    #更新map

        return count