BinarySearch 0805 Binary Sublist with Target Sum

Problem statement

https://binarysearch.com/problems/Binary-Sublist-with-Target-Sum/

Solution

Special case of Leetcode 0560 Subarray Sum Equals K, but here values are 0 and 1.

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