C++で等しいXORの2つの配列を形成できるトリプレットを数える

整数の配列arrがあるとします。 i、j、kのような3つのインデックスを選択します。ここで、（0 <=i

したがって、入力が[2,3,1,6,7]の場合、トリプレットは（0,1,2）、（0,2,2）、（2,3）であるため、出力は4になります。 、4）および（2,4,4）

これを解決するには、次の手順に従います-

• ret：=0

• n：=arrのサイズ

• 初期化i：=1の場合、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]

• 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