930. Binary Subarrays With Sum

Problem

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:

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

Problem Summary

Given an array whose elements are only 0 and 1. Ask how many subarrays of this array have sum S.

Solution Approach

This problem is also a sliding window problem. Continuously add the value on the right until the total sum equals S. The sum in the interval [i,j] can be equal to the sum of [0,j] minus the sum of [0,i-1]. Continuously record in freq the number of combination methods that can make the sum equal to sum. For example, freq[1] = 2 means there are two combination methods for sum 1 (possibly 1 and 1,0 or 0,1; this problem only cares about the total number of combinations and does not require outputting the specific combination pairs). The approach to this problem is to continuously accumulate. If a situation greater than S is encountered, look up the excess value in freq to see how many situations the excess value may be composed of. Once the sum equals S, the situations exceeding S afterward will become more and more numerous (because it is continuously accumulating, and the total sum will only get larger), so continuously checking the freq table is enough.

Code

package leetcode

import "fmt"

func numSubarraysWithSum(A []int, S int) int {
	freq, sum, res := make([]int, len(A)+1), 0, 0
	freq[0] = 1
	for _, v := range A {
		t := sum + v - S
		if t >= 0 {
			// The total sum has excess; need to subtract t, and there are freq[t] ways to remove it
			res += freq[t]
		}
		sum += v
		freq[sum]++
		fmt.Printf("freq = %v sum = %v res = %v t = %v\n", freq, sum, res, t)
	}
	return res
}