資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告