在由若干 0 和 1 组成的数组 A 中,有多少个和为 S 的非空子数组。
示例:
输入:A = [1,0,1,0,1], S = 2
输出:4
解释:
如下面黑体所示,有 4 个满足题目要求的子数组:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
提示:
A.length <= 30000
0 <= S <= A.length
A[i] 为 0 或 1
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-subarrays-with-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目: LeetCode 523. 连续的子数组和(求余 哈希) LeetCode 525. 连续数组(前缀和+哈希) LeetCode 560. 和为K的子数组(前缀和差分) LeetCode 974. 和可被 K 整除的子数组(哈希map) LeetCode 1248. 统计「优美子数组」(要复习)
class Solution {
public:
int numSubarraysWithSum(vector<int>& A, int S) {
int n = A.size(), sum = 0, i = 0, count = 0;
unordered_map<int,int> m;//sum, 有多少个
m[0] = 1;//等于0的有1个
for(i = 0; i < n; i++)
{
sum += A[i];//前缀和
if(m.find(sum-S) != m.end())
count += m[sum-S];
//前缀和减去S后的前缀和存在,中间段就是和为S的
m[sum]++;
}
return count;
}
};
124 ms 30.5 MB