สมมติว่ามีอาร์เรย์ A เท่ากับ 0 และ 1 วินาที เราต้องค้นหาว่าอาร์เรย์ย่อยที่ไม่ว่างมีจำนวนเท่าใดที่มีผลรวม 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, set j :=0 และ set ret :=0
-
สำหรับผมอยู่ในช่วง 0 ถึงขนาด A
-
ลด x โดย A[i]
-
ในขณะที่ x <0
-
เพิ่ม x โดย A[j], เพิ่ม j ขึ้น 1
-
-
ret :=ret + i – j + 1
-
-
รีเทิร์น
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ret :=atMost(A, S) – atMost(A, S – 1)
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น &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
