Algorithm
Problem Name: 930. Binary Subarrays With Sum
Problem Link: https://leetcode.com/problems/binary-subarrays-with-sum/
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 * 104nums[i]is either0or1.0 <= goal <= nums.length
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const numSubarraysWithSum = function(A, S) {
if(A === null || A.length == 0) return 0;
const freq = new Array(A.length + 1).fill(0)
let ans = 0;
let sum = 0;
for(let i = 0; i < A.length; i++> {
sum += A[i];
let index = sum - S;
if(index >= 0) ans += freq[index];
if(sum == S) ans++;
freq[sum]++;
}
return ans;
};
Input
nums = [1,0,1,0,1], goal = 2
Output
4
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numSubarraysWithSum(self, A, S):
res, sm, sums = 0, 0, collections.defaultdict(int)
for a in A:
sm += a
res += sums[sm - S] + (sm == S)
sums[sm] += 1
return res
Input
nums = [1,0,1,0,1], goal = 2
Output
4