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
}