Python O(n) Solution using Map

  • 1
    def subarraySum(self, nums, k):
        dic = {0:1}
        res, total = 0, 0
        for i in range(len(nums)):
            total += nums[i]
            res += dic.get(total-k, 0)
            dic[total] = dic.get(total, 0) + 1
        return res

    initial with {0:1} in case of total == k.
    we calculate the sum from the first element, we record the appearance time of each different sum.
    we try to find the (sum-k), since if k + (some sum appeared already) = sum means that k could equal to (sum-some sum appeared already) this continuous subarrays

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.