Skip to content

930. Binary Subarrays With Sum

Difficulty Topics

Description

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

 

Example 1:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The 4 subarrays are bolded and underlined below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

Example 2:

Input: nums = [0,0,0,0,0], goal = 0
Output: 15

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • nums[i] is either 0 or 1.
  • 0 <= goal <= nums.length

Solution

binary-subarrays-with-sum.py
class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        count = Counter()
        count[0] = 1
        res = s = 0

        for x in nums:
            s += x

            res += count[s - goal]

            count[s] += 1

        return res