题目描述
在由若干 0 和 1 组成的数组 A 中,有多少个和为 S 的非空子数组。
样例
输入:A = [1,0,1,0,1], S = 2
输出:4
算法1
(哈希表优化前缀和) $O(n)$
在枚举前缀和的过程中,统计前缀和出现的个数,寻找前缀和sum - S 是否在哈希表中,如果在
则累加对应的个数。初始化hash[0] = 1
时间复杂度 $O(n)$
C++ 代码
class Solution {
public:
int numSubarraysWithSum(vector<int>& A, int S) {
if (A.empty()) { return 0; }
int n = A.size(), ans = 0, sum = 0;
unordered_map<int, int> hash;
hash[0] = 1;
for (int i = 0; i < n; i++) {
sum += A[i];
if (hash.count(sum - S)) {
ans += hash[sum - S];
}
hash[sum]++;
}
return ans;
}
};