930. Binary Subarrays With Sum

Problem Link

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

---

Python3

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        N = len(nums)
        
        def atMost(k):
            if k < 0: return 0
 
            i = curr = res = 0
 
            for j, x in enumerate(nums):
                curr += x
 
                while curr > k:
                    curr -= nums[i]
                    i += 1
                
                res += (j - i + 1)
            
            return res
        
        return atMost(goal) - atMost(goal - 1) # to find the number of subarrays with exact "goal"