LeetCode Solutions
930. Binary Subarrays With Sum
Time: Space:
class Solution {
public:
int numSubarraysWithSum(vector<int>& A, int S) {
int ans = 0;
int prefix = 0;
unordered_map<int, int> count{{0, 1}};
for (int a : A) {
prefix += a;
if (count.count(prefix - S))
ans += count[prefix - S];
++count[prefix];
}
return ans;
}
};
class Solution {
public int numSubarraysWithSum(int[] A, int S) {
int ans = 0;
int prefix = 0;
Map<Integer, Integer> count = new HashMap<>();
count.put(0, 1);
for (int a : A) {
prefix += a;
if (count.containsKey(prefix - S))
ans += count.get(prefix - S);
count.put(prefix, count.getOrDefault(prefix, 0) + 1);
}
return ans;
}
}
class Solution:
def numSubarraysWithSum(self, A: List[int], S: int) -> int:
ans = 0
prefix = 0
count = Counter({0: 1})
for a in A:
prefix += a
ans += count[prefix - S]
count[prefix] += 1
return ans