Binary Subarrays With Sum

Problem Statement

In the given problem, you are provided with a binary array named nums and an integer goal. The main task is to determine the number of contiguous subarrays within nums that sum up to exactly the goal. A subarray is defined as a continuous subset of the array, and it must be non-empty. This type of problem is commonly associated with array manipulation and presents an opportunity to explore various techniques to calculate subarray sums efficiently.

Examples

Example 1

Input:

nums = [1,0,1,0,1], goal = 2

Output:

4

Explanation:

The 4 subarrays are bolded and underlined below:

[1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1]

Example 2

Input:

nums = [0,0,0,0,0], goal = 0

Output:

15

Constraints

• 1 <= nums.length <= 3 * 104
• nums[i] is either 0 or 1.
• 0 <= goal <= nums.length

Approach and Intuition

Understanding the problem with the examples given can help determine an optimal approach to the solution:

1. Utilizing the Prefix Sum Technique:

   • The prefix sum array helps in quickly calculating the sum of any subarray.
   • For any subarray nums[i:j+], the sum can be retrieved by prefix[j+1] - prefix[i], where prefix[k] is the sum of elements from the start of nums up to but not including index k.
   • The challenge then reduces to finding pairs of indices (i, j) such that prefix[j+1] - prefix[i] = goal.

2. Using a hashmap to optimize:

   • While iterating over the array, you can maintain a running sum and use a hashmap to store the frequency of each sum encountered up to the current point.
   • For each element in nums, update the running sum. Check how many times (running sum - goal) has appeared in the hashmap because it indicates the number of subarrays ending at the current index that have the required goal.
   • This method ensures that we only pass through the array once, maintaining efficiency.

3. Breaking down the examples:

   • Example 1: In the array [1,0,1,0,1] with goal = 2:
     • The possible subarrays achieving this sum are: [1,0,1], [1,0,1], [0,1,0,1], [1,0,1]. Each of these sequences sum up to 2, thus giving 4 as the output.
   • Example 2: In the array [0,0,0,0,0] with a goal = 0:
     • Here, several single-element subarrays and multi-element subarrays sum to 0, totaling up to 15 subarrays.

Through the hashmap and prefix sum technique, it's feasible to solve the problem with a linear time complexity relative to the size of nums, ensuring efficient processing even for larger arrays. This approach leverages the characteristics of subarray sums and hash-based storage for past computed sums to streamline the search for subarrays that meet the desired goal.

Solutions

class Solution {
public:
    int countTargetSubarrays(vector<int>& arr, int target) {
        int left = 0;
        int zeroCount = 0;
        int sum = 0;
        int result = 0;
            
        for (int right = 0; right < arr.size(); ++right) {
            sum += arr[right];
                
            while (left < right && (arr[left] == 0 || sum > target)) {
                if (arr[left] == 1) {
                    zeroCount = 0;
                } else {
                    zeroCount += 1;
                }
                    
                sum -= arr[left];
                left += 1;
            }
                
            if (sum == target) {
                result += 1 + zeroCount;
            }
        }
            
        return result;
    }
};