Search code examples
pythonarraysalgorithmsumsub-array

not able to solve edge case in number of contiguous subarrays with sum k


I have been trying to solve the "Subarray Sum Equals K" problem on leetcode. However I am not able to solve some test cases with the following code:

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

Solution

  • Found this solution on 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
    

    Adding on why your solution won't work, is because your TotalSum never resets. Therefore you detect either 0 or 1 solutions.