สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม arr เราต้องการเลือกดัชนีสามตัวเช่น i, j และ k โดยที่ (0 <=i
ดังนั้น หากอินพุตเป็น [2,3,1,6,7] ผลลัพธ์จะเป็น 4 เนื่องจากแฝดสามคือ (0,1,2), (0,2,2), (2,3 ,4) และ (2,4,4)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ยกเลิก :=0
n :=ขนาดของ arr
สำหรับการเริ่มต้น i :=1 เมื่อฉัน
กำหนดหนึ่งแผนที่ m
x1 :=0, x2 :=0
สำหรับการเริ่มต้น j :=i - 1 เมื่อ j>=0, อัปเดต (ลด j โดย 1) ให้ทำ -
x1 :=x1 XOR arr[j]
(เพิ่ม m[x1] ขึ้น 1)
สำหรับการเริ่มต้น j :=i เมื่อ j
x2 :=x2 XOR arr[j]
ret :=ret + m[x2]
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countTriplets(vector<int>& arr) {
int ret = 0;
int n = arr.size();
for (int i = 1; i < n; i++) {
map<int, int> m;
int x1 = 0;
int x2 = 0;
for (int j = i - 1; j >= 0; j--) {
x1 = x1 ^ arr[j];
m[x1]++;
}
for (int j = i; j < n; j++) {
x2 = x2 ^ arr[j];
ret += m[x2];
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,3,1,6,7};
cout << (ob.countTriplets(v));
} อินพุต
{2,3,1,6,7} ผลลัพธ์
4
