在 C++ 中计算可以形成两个相等异或数组的三元组
c++server side programmingprogramming
假设我们有一个整数数组 arr。我们想要选择三个索引，如 i、j 和 k，其中 (0 <= i < j <= k < N)，N 是数组的大小。 a 和 b 的值如下: a = arr[i] XOR arr[i + 1] XOR ... XOR arr[j - 1] b = arr[j] XOR arr[j + 1] XOR ... XOR arr[k] 我们必须找到三元组 (i, j, k) 的数量，其中 a 与 b 相同。
因此，如果输入为 [2,3,1,6,7]，则输出将为 4，因为三元组为 (0,1,2)、(0,2,2)、(2,3,4) 和 (2,4,4)
为了解决这个问题，我们将遵循以下步骤 −
ret := 0
n := arr 的大小
初始化 i := 1，当 i < n，更新(将 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 < n，更新(将 j 增加 1)，执行 −
x2 := x2 XOR arr[j]
ret := ret + m[x2]
return ret
示例
让我们看看下面的实现以便更好地理解 −
#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
