Jianbo Dai's

lc560.和为K的子数组

 
  • Dec 08, 2020

题目链接

这个题，一开始是觉得应该用滑动窗口做，或者动态规划做，可是思路感觉不是特别清晰。看了答案之后才懂的，如1所示是未优化过的，这个算法的时间复杂度是O（N），空间复杂度是O（N）。这个思路简单地说就是用前缀和，在遍历数组的过程中，将前缀和一一记下，并且判断某个时刻所对应的“k-前缀和”的值是否在字典中以及为多少，将该数字加到答案上。啊话说不知道为什么，用现成的defaultdict反而速度快一点。

class Solution:
    def subarraySum1(self, nums: List[int], k: int) -> int:
        preSum, ans = 0, 0
        preSumFreq = collections.defaultdict(int)
        preSumFreq[0] += 1
        for i in range(len(nums)):
            preSum += nums[i]
            ans += preSumFreq[preSum-k]
            preSumFreq[preSum] += 1
        return ans

    def subarraySum2(self, nums: List[int], k: int) -> int:
        preSum, ans = 0, 0
        preSumFreq = {0: 1}
        for i in range(len(nums)):
            preSum += nums[i]
            if (preSum - k) in preSumFreq:
                ans += preSumFreq[preSum-k]
            if preSum in preSumFreq:
                preSumFreq[preSum] += 1
            else:
                preSumFreq[preSum] = 1
        return ans
Search