930. Binary Subarrays With Sum

-
https://leetcode.com/problems/binary-subarrays-with-sum/

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.
----
Intuition

Prefix sum approach
If difference of prefix sum at any two indices == target => sum of elements between those two indices == target => increment ans by 1

If the same prefix sum appears again.. (can happen in binary array or array with negative numbers), then ans += number of previous prefix sums with that sum

Track the prefix sum, and # of times it appears in a hash map
Seed the map with key = 0, value = 1 (*)

Traverse left to right

if (sum >= s)
   ans += map.get(sum - s)

map.put(sum, map.get(sum) + 1)


(*) When prefix sum = target, this enables us to add 1 to output
---
Time - O(n)
Space - O(n)
---
Related problems
---