BinarySearch 0352 Number of Sublists With Sum of Target

Problem statement

https://binarysearch.com/problems/Number-of-Sublists-With-Sum-of-Target/

Solution

Equal to Leetcode 0560 Subarray Sum Equals K

Complexity

Time and space is O(n).

Code

class Solution:
    def solve(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