数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中子数组和为 S 的十进制子数组
假设给定一个由 0 和 1 组成的数组 A，我们必须找出有多少个非空子数组的总和为 S？因此，如果输入类似于 [1,0,1,0,1]，并且 S = 2，那么结果将为 4，因为子数组为 [1,0,1,0,1]，[1,0,1,0,1]，[1,0,1,0, 1]，[1,0,1,0,1]。
为求解此问题，我们将遵循以下步骤 -
定义一个名为 atMost() 的方法，它将采用数组 A 和整数 x
如果 x < 0，则返回 0，设置 j := 0 并设置 ret := 0
对于 i 在 0 到 A 的范围
将 x 减去 A[i]
当 x < 0
将 x 加上 A[j]，将 j 加 1
ret := ret + i – j + 1
返回 ret
在主方法中执行以下操作 -
ret := atMost(A, S) – atMost(A, S – 1)
返回 ret
让我们看看以下实现，以更好地理解 &mius；
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int atMost(vector <int>& A, int x){
if(x < 0) return 0;
int j = 0;
int ret = 0;
for(int i = 0; i < A.size(); i++){
x -= A[i];
while(x < 0){
x += A[j];
j++;
}
ret += i - j + 1;
}
return ret;
}
int numSubarraysWithSum(vector<int>& A, int S) {
return atMost(A, S) - atMost(A, S - 1);
}
};
main(){
vector<int> v1 = {1,0,1,0,1};
Solution ob;
cout << (ob.numSubarraysWithSum(v1, 2));
}输入
[1,0,1,0,1]
输出
4
更新于： 30-04-2020
445 次浏览
广告