python - 无法解决总和为 k 的连续子数组中的边缘情况

Question

我一直在尝试解决 leetcode 上的“子数组和等于 K”问题。但是我无法使用以下代码解决一些测试用例:

from collections import defaultdict
class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        sumTable = defaultdict(lambda : 0) 

        count = 0
        totalSum = 0
        for i in range(0,len(nums)):
            totalSum += nums[i]
            if(totalSum==k):
                count += 1
            sumTable[totalSum] += 1

        for key in sumTable:
            # print(key)
            if (key-k) in sumTable:
                    count += sumTable[key-k]

        return count

Answer 1

在 Github 上找到了这个解决方案

import collections
class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        result = 0
        accumulated_sum = 0
        lookup = collections.defaultdict(int)
        lookup[0] += 1
        for num in nums:
            accumulated_sum += num
            result += lookup[accumulated_sum - k]
            lookup[accumulated_sum] += 1
        return result

补充一下为什么您的解决方案不起作用，是因为您的 TotalSum 永远不会重置。因此，您检测到 0 个或 1 个解决方案。