C++程序计算唯一三元组的XOR为零

给定没有重复项的N个数字，计算唯一三元组（ai,aj,ak）的数量，使它们的XOR为0。如果三元组中的所有三个数字都是唯一的，则称其为唯一的三元组。

示例：

输入：a[] = {1, 3, 5, 10, 14, 15};
输出：2
解释：{1，14，15}和{5，10，15}是其XOR为0的唯一三元组。{1，14，15}和所有其他组合的1,14,15都视为一种。

输入：a[] = {4，7，5，8，3，9};
输出：1
解释：{4, 7, 3}是其XOR为0的唯一三元组

朴素方法： 一个朴素的方法是运行三个内嵌循环，第一个运行从0到n，第二个运行从i+1到n，最后一个从j+1到n，以获取唯一的三元组。计算ai, aj, ak的XOR，检查其是否等于0。如果是，则增加计数。

时间复杂度：O(n3)

高效方法： 一种有效的方法是使用XOR的属性之一：两个相同数字的XOR结果为0。因此，我们只需要计算唯一的对的XOR，如果计算的XOR是数组元素之一，则获得其XOR为0的三元组。下面给出计算唯一三元组数量的步骤：

以下是此方法的完整算法：

使用哈希表标记所有数组元素。
运行两个嵌套循环，一个从i-n-1，另一个从i+1-n，以获取所有对。
获取对的XOR。
检查XOR是否为数组元素而不是ai或aj。
如果条件成立，则增加计数。
返回count / 3，因为我们只想要唯一的三元组。因为i-n和j + 1-n给我们提供了唯一的对，但不是三元组，所以进行count / 3以删除其他两个可能的组合。

以下是上述想法的实现：

// CPP program to count the number of
// unique triplets whose XOR is 0
#include <bits/stdc++.h>
using namespace std;
 
// function to count the number of
// unique triplets whose xor is 0
int countTriplets(int a[], int n)
{
    // To store values that are present
    unordered_set<int> s;
    for (int i = 0; i < n; i++)
        s.insert(a[i]);
     
    // stores the count of unique triplets
    int count = 0;
     
    // traverse for all i, j pairs such that j>i
    for (int i = 0; i < n-1; i++) {
        for (int j = i + 1; j < n; j++) {
 
          // xor of a[i] and a[j]
          int xr = a[i] ^ a[j];
     
          // if xr of two numbers is present,
          // then increase the count
          if (s.find(xr) != s.end() && xr != a[i] &&
                                       xr != a[j])
            count++;
        }
    }
     
    // returns answer
    return count / 3;
}
 
// Driver code to测试上述函数的代码：

// Driver code to test above function
int main()
{
    int a[] = {1, 3, 5, 10, 14, 15};
    int n = sizeof(a) / sizeof(a[0]);  
    cout << countTriplets(a, n);   
    return 0;
}

输出：

时间复杂度： O（n2）

辅助空间： 对于unordered_set为O（n）