Binary Subarrays With Sum

Description

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

 

Example 1:

Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

 

Note:

1. A.length <= 30000
2. 0 <= S <= A.length
3. A[i] is either 0 or 1.

Solution(javascript)

/*
 * @lc app=leetcode id=930 lang=javascript
 *
 * [930] Binary Subarrays With Sum
 */

// @lc code=start
/** Prefix Sum
 * @param {number[]} A
 * @param {number} S
 * @return {number}
 */
const numSubarraysWithSum = function (A, S) {
  const map = { }
  let sum = 0
  let count = 0
  for (const num of A) {
    map[sum] = (map[sum] || 0) + 1
    sum += num
    count += map[sum - S] || 0
  }
  return count
}