Loading content...
You are given an array nums consisting exclusively of zeros and ones (a binary array), along with an integer goal representing a target sum. Your task is to determine the total count of non-empty contiguous segments (subarrays) within the array whose elements add up exactly to the specified goal.
A contiguous segment is defined as a sequence of consecutive elements from the array. Note that segments can overlap, and each valid segment should be counted separately even if different segments contain the same elements at different positions.
The challenge lies in efficiently counting all such segments, especially when the array is large. A naive approach of checking every possible segment would be too slow for larger inputs, so consider techniques like prefix sums combined with hash tables, or the sliding window approach for optimal performance.
nums = [1,0,1,0,1]
goal = 24There are 4 contiguous segments that sum to 2: • Segment [0..2]: [1,0,1] → sum = 2 • Segment [0..3]: [1,0,1,0] → sum = 2 • Segment [1..4]: [0,1,0,1] → sum = 2 • Segment [2..4]: [1,0,1] → sum = 2
nums = [0,0,0,0,0]
goal = 015Every contiguous segment of an all-zeros array sums to 0. For an array of length 5, the total number of non-empty contiguous segments is n×(n+1)/2 = 5×6/2 = 15.
nums = [1,0,1,0]
goal = 16The 6 contiguous segments with sum 1 are: • [0..0]: [1] → sum = 1 • [0..1]: [1,0] → sum = 1 • [1..2]: [0,1] → sum = 1 • [1..3]: [0,1,0] → sum = 1 • [2..2]: [1] → sum = 1 • [2..3]: [1,0] → sum = 1
Constraints