สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มและจำนวนเต็ม k เราจำเป็นต้องค้นหาจำนวนทั้งหมดของอาร์เรย์ย่อยแบบต่อเนื่องซึ่งมีผลรวมเท่ากับ k ดังนั้นหาก nums array คือ [1, 1, 1] และ k คือ 2 ผลลัพธ์จะเป็น 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดหนึ่งแผนที่เรียกว่า sums, temp :=0, sums[0] :=1 and ans :=0
- สำหรับ i ในช่วง 0 ถึงขนาดของอาร์เรย์
- อุณหภูมิ :=อุณหภูมิ + n[i]
- ถ้าผลรวมมี k – temp แล้ว
- ans :=ans + sums[k - temp]
- เพิ่มมูลค่าของผลรวม[-temp] ขึ้น 1
- คืนสินค้า
ตัวอย่าง(C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& n, int k) {
unordered_map <int, int> sums;
int temp = 0;
sums[0] = 1;
int ans =0;
for(int i =0;i<n.size();i++){
temp+= n[i];
if(sums.find(k-temp)!=sums.end()){
ans += sums[k-temp];
}
sums[-temp]++;
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,1,1};
cout << (ob.subarraySum(v, 2));
} อินพุต
[1,1,1] 2
ผลลัพธ์
2
