Binary Subarrays With Sum

Similar Problems:

- Subarray Product Less Than K
- CheatSheet: Leetcode For Code Interview
- Tag: #subarray, #presum, #inspiring, #classic

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// Blog link: https://code.dennyzhang.com/binary-subarrays-with-sum // Basic Ideas: Presum + Dynamic Programming // Count how many subarray ends with current item // Complexity: Time O(n), Space (n) func numSubarraysWithSum(A []int, S int) int { res, preSum := 0, 0 h := map[int]int{0: 1} for _, v := range A { preSum += v res += h[preSum - S] h[preSum]++ } return res }