Description
Given a binary array nums and integer goal, return the number of non-empty subarrays with a sum equal to goal.
Examples
Input:
nums = [1,0,1,0,1], goal = 2Output:
4Explanation:
Four subarrays sum to 2.
Input:
nums = [1,1,0,1], goal = 2Output:
3Explanation:
The subarrays of [1,1,0,1] that sum to 2 are: [1,1] at indices 0-1, [1,0,1] at indices 0-2, and [1,0,1] at indices 1-3. That gives 3 subarrays.
Input:
nums = [0,1,0,0,1], goal = 1Output:
9Explanation:
Nine subarrays sum to 1: [1] at index 1, [1] at index 4, [0,1] (0-1), [1,0] (1-2), [0,1,0] (0-2), [1,0,0] (1-3), [0,0,1] (2-4), [0,1,0,0] (0-3), and [1,0,0,1] (1-4) has sum 2, not 1. Let me recount: single [1] at positions 1 and 4 (2 subarrays), then subarrays containing exactly one 1: [0,1] (0-1), [1,0] (1-2), [1,0,0] (1-3), [0,1,0] (0-2), [0,1,0,0] (0-3), [0,1] (3-4), [0,0,1] (2-4). That's 9 total subarrays with sum 1.
Constraints
- •
1 ≤ nums.length ≤ 3 × 10⁴