Binary Subarrays With Sum (Exactly K Trick)

Problem

Given a binary array and an integer goal, count the number of contiguous subarrays whose sum equals goal exactly.

Input:  nums = [1,0,1,0,1], goal = 2
Output: 4

Python Solution

def num_subarrays_with_sum(nums, goal):
    def at_most(target):
        if target < 0:
            return 0
        left = 0
        window_sum = 0
        count = 0
        for right in range(len(nums)):
            window_sum += nums[right]
            while window_sum > target:
                window_sum -= nums[left]
                left += 1
            count += right - left + 1
        return count

    return at_most(goal) - at_most(goal - 1)

C++ Solution

int atMost(vector<int>& nums, int target) {
    if (target < 0) return 0;
    int left = 0, windowSum = 0, count = 0;
    for (int right = 0; right < nums.size(); right++) {
        windowSum += nums[right];
        while (windowSum > target) {
            windowSum -= nums[left];
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

int numSubarraysWithSum(vector<int>& nums, int goal) {
    return atMost(nums, goal) - atMost(nums, goal - 1);
}

Java Solution

class Solution {
    private int atMost(int[] nums, int target) {
        if (target < 0) return 0;
        int left = 0, windowSum = 0, count = 0;
        for (int right = 0; right < nums.length; right++) {
            windowSum += nums[right];
            while (windowSum > target) {
                windowSum -= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }

    public int numSubarraysWithSum(int[] nums, int goal) {
        return atMost(nums, goal) - atMost(nums, goal - 1);
    }
}

Complexity

Time: O(n) — two linear sliding-window passes (atMost goal, atMost goal-1). Space: O(1) — only running sums and pointers. The "exactly K" pattern (atMost(K) - atMost(K-1)) is a reusable trick for any sliding-window-with-sum-constraint problem.