Problem statement

https://leetcode.com/problems/subarray-sum-equals-k/

Solution

Evaluate cumulative sums and then for each cumulative sum si check if we already have si - k in our dictionary and how many times. If we do not found it, just increase frequency by one. Be careful, we need to traverse cumulative sums one by one, we can not just evaluate frequencies, in this way we can have both k and -k subarrays.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def subarraySum(self, nums, k):
        acc = [0] + list(accumulate(nums))
        count = 0
        d = defaultdict(int)
        for i in acc:
            if (i-k) in d:
                count += d[i-k] 
            d[i] += 1
        return count