文章目錄
- 1. 題目
- 2. 解題
1. 題目
在由若干 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
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2. 解題
類似題目：
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
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/61527.html
標籤：其他