930.md

930. Binary Subarrays With Sum

Solution 1 (time O(n), space O(n))

class Solution(object):
    def numSubarraysWithSum(self, nums, goal):
        """
        :type nums: List[int]
        :type goal: int
        :rtype: int
        """
        d = collections.defaultdict(int)
        d[0] = 1
        ans = 0
        cur_sum = 0
        for num in nums:
            cur_sum += num
            ans += d[cur_sum - goal]
            d[cur_sum] += 1
        return ans