使用C++找到XOR为零的独特三元组的数量

什么是XOR

XOR就是异或操作，是一种比较特殊的位运算符。它的英文全称叫Exclusive OR，意思是“异或”。如果在计算机中使用二进制数值来进行这种位运算的话，实际上是先将两个二进制数按位分别取反，然后再进行按位与操作。如果两个数的某一位相同，结果为0，否则为1。

int a = 5;    //二进制：101
int b = 3;    //二进制：011
int c = a ^ b;    //二进制：110

上述代码中，c的二进制结果为110，即6。

什么是独特三元组

独特三元组指的是三个数a、b、c，满足a ^ b ^ c = 0且a、b、c互不相同。

如何找到XOR为零的独特三元组数量

暴力枚举法

最直接的思路就是枚举所有可能的三元组：使用三重循环遍历所有数字，然后依次进行异或运算，判断是否符合条件，这种方法的时间复杂度为O(n^3)。

int countTriplets_bruteforce(vector& arr) {
    int n = arr.size(), ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if ((arr[i] ^ arr[j] ^ arr[k]) == 0) {
                    ans++;
                }
            }
        }   
    }
    return ans;
}

使用哈希表

我们可以使用一个哈希表来记录前缀异或值对应的出现次数。在遍历数组的过程中，使用prefix变量记录前面所有数字的异或值，然后从哈希表中查找表项key=prefix ^ arr[i]的出现次数，即为以当前数字arr[i]作为右端点的符合条件的三元组数量。哈希表中记录的是前面所有数字的异或值，这样我们就避免了暴力枚举每一个三元组的复杂度，时间复杂度降到了O(n^2)。

int countTriplets_hash(vector& arr) {
    int n = arr.size(), ans = 0, prefix = 0;
    unordered_map cnt, total;
    cnt[0] = 1;
    for (int i = 0; i < n; i++) {
        prefix ^= arr[i];
        ans += cnt[prefix] * i - total[prefix];
        cnt[prefix]++;
        total[prefix] += (i + 1);
    }
    return ans;
}

上述代码中，我们使用了两个哈希表，cnt记录前缀异或值出现的次数，total记录前缀异或值出现的位置之和。ans记录的是当前符合条件的三元组数量。

总结

基本上所有的解法都可以通过对位运算的合理运用来避免通过暴力枚举所有可能的三元组来判断是否符合条件。这样能够提高时间复杂度，显著地降低算法运行的时间。具体来说，使用哈希表是非常高效且易于理解的解法。简单来说，前缀异或值的特性是相同的数字异或之后得到的数字为0，因此通过使用哈希表保存前缀异或值对应的出现次数，就可以方便地通过查找hash[prefix ^ arr[i]]来计算以当前数字作为右端点的符合条件的三元组数量，也就是可以得到满足a ^ b ^ c = 0的三元组数量。