计算可以在C ++中形成两个相等XOR数组的三元组

假设我们有一个整数数组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），-

• x2：= x2 XOR arr [j]

• ret：= ret + m [x2]

• x1：= x1 XOR arr [j]

• （将m [x1]增加1）

• 定义一张映射

• x1：= 0，x2：= 0

• 对于初始化j：= i-1，当j> = 0时，更新（将j减1），-

• 对于初始化j：= i，当j <n时，更新（将j增加1），-

• 返回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