Leetcode 0930. Binary Subarrays With Sum

Problem statement

https://leetcode.com/problems/binary-subarrays-with-sum/

Solution

We can use cumulative sums and then it is equivalent to 2sum problem.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def numSubarraysWithSum(self, A, S):
        cnt, ans = Counter([0]), 0
        for el in accumulate(A):
            ans += cnt[el - S]
            cnt[el] += 1
        return ans