leetcode560. 和为 K 的子数组

因为前缀和相减代表数组中某一段元素的和，所以我们统计前缀和并记录前缀和出现的次数
pre[i+1] - presum[j] = k。是i到j这一段元素的和等于k，
pre[i+1] -k = presum[j] 所以以i为结尾的满足条件的个数就是前缀和presum[j]的个数也就是mp[presum-k]

def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        mp = dict()
        mp[0] = 1
        count = 0
        presum = 0
        for num in nums:
            presum += num
            if presum - k in mp:
                count += mp[presum-k]
            mp[presum] = mp.get(presum,0) + 1
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        mp = dict()
        presum = [0]
        count = 0
        for num in nums:
            presum.append(presum[-1]+num)
        for i in range(len(nums)+1):
            if presum[i] - k in mp:
                count += mp[presum[i]-k]
            mp[presum[i]] = mp.get(presum[i],0)+1
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16