Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/930.html
930. Binary Subarrays With Sum
Level
Medium
Description
In an array A
of 0
s and 1
s, 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 either0
or1
.
Solution
Use a map to count the number of subarrays starting from index 0 that have sum equal to a given value.
If S
is 0, then for each possible sum in the map, count the number of subarrays of the sum. If there are k
such subarrays, then the number of non-empty subarrays obtained from such subarrays is k * (k - 1) / 2
. Count the number of non-empty subarrays with sum 0 from all possible sums in the map.
If S
is positive, then for each pair (i, i + S)
such that i >= 0
and i + S
doesn’t exceed the maximum possible sum (which is the sum of all numbers in the array), let count1
and count2
be the numbers of subarrays starting from index 0 that have sum i
and sum i + S
respectively, and the number of non-empty subarrays with sum S
for the pair (i, i + S)
is count1 * count2
. Count the number of non-empty subarrays with sum S
from all possible sums in the map.
-
class Solution { public int numSubarraysWithSum(int[] A, int S) { if (A == null || A.length == 0) return 0; Map<Integer, Integer> sumCountMap = new HashMap<Integer, Integer>(); int length = A.length; int beginIndex = 0; int curSum = A[0]; for (int i = 1; i < length; i++) { if (A[i] == 1) { sumCountMap.put(curSum, i - beginIndex); curSum++; beginIndex = i; } } sumCountMap.put(curSum, length - beginIndex); int totalCount = 0; sumCountMap.put(0, sumCountMap.getOrDefault(0, 0) + 1); if (S == 0) { Set<Integer> keySet = sumCountMap.keySet(); for (int num : keySet) { int count = sumCountMap.get(num); totalCount += count * (count - 1) / 2; } return totalCount; } else { int minSum = A[0], maxSum = curSum; int upper = maxSum - S; for (int i = 0; i <= upper; i++) { int count1 = sumCountMap.get(i), count2 = sumCountMap.get(i + S); totalCount += count1 * count2; } return totalCount; } } }
-
// OJ: https://leetcode.com/problems/binary-subarrays-with-sum/ // Time: O(N) // Space: O(N) class Solution { public: int numSubarraysWithSum(vector<int>& A, int goal) { unordered_map<int, int> m{ {0,-1} }; // count of 1s -> index int ans = 0; for (int i = 0, N = A.size(), sum = 0; i < N; ++i) { sum += A[i]; if (m.count(sum) == 0) m[sum] = i; if (goal == 0) ans += i - m[sum]; else if (sum - goal >= 0) ans += m[sum - goal + 1] - m[sum - goal]; } return ans; } };
-
class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: i1 = i2 = s1 = s2 = j = ans = 0 n = len(nums) while j < n: s1 += nums[j] s2 += nums[j] while i1 <= j and s1 > goal: s1 -= nums[i1] i1 += 1 while i2 <= j and s2 >= goal: s2 -= nums[i2] i2 += 1 ans += i2 - i1 j += 1 return ans ############ class Solution(object): def numSubarraysWithSum(self, A, S): """ :type A: List[int] :type S: int :rtype: int """ N = len(A) tsum = [0] * (N + 1) for i in range(1, N + 1): tsum[i] = tsum[i - 1] + A[i - 1] res = 0 for i in range(1, N + 1): remain = tsum[i] - S if remain < 0: continue left = bisect.bisect_left(tsum, remain) right = bisect.bisect_right(tsum, remain) right = min(i, right) res += right - left return res
-
func numSubarraysWithSum(nums []int, goal int) int { i1, i2, s1, s2, j, ans, n := 0, 0, 0, 0, 0, 0, len(nums) for j < n { s1 += nums[j] s2 += nums[j] for i1 <= j && s1 > goal { s1 -= nums[i1] i1++ } for i2 <= j && s2 >= goal { s2 -= nums[i2] i2++ } ans += i2 - i1 j++ } return ans }
-
/** * @param {number[]} nums * @param {number} goal * @return {number} */ var numSubarraysWithSum = function (nums, goal) { let i1 = 0, i2 = 0, s1 = 0, s2 = 0, j = 0, ans = 0; const n = nums.length; while (j < n) { s1 += nums[j]; s2 += nums[j]; while (i1 <= j && s1 > goal) s1 -= nums[i1++]; while (i2 <= j && s2 >= goal) s2 -= nums[i2++]; ans += i2 - i1; ++j; } return ans; };