LeetCode: Binary Subarrays With Sum Posted on October 28, 2018July 26, 2020 by braindenny Binary Subarrays With Sum Similar Problems: Subarray Product Less Than K CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups 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: // 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 } Post Views: 0