1442.形成两个异或相等数组的三元组数目

题目描述：

解：

形如arr[i] op arr[i+1] … op arr[j-1]的情况，都可以考虑用前缀和的方式来优化数组，当然，这里并非是前缀和而是前缀异或。
前缀和的容斥是用减法实现的，前缀异或的容斥是用一个数异或本身等于0这个性质来实现。
所以，我们先将原数组O(n)的处理成前缀异或数组。
然后开始暴力…(其实还可以继续优化的）
遍历i,j,k,用 xor[j-1] ^ xor[i-1] 来表示 arr[i]^arr[i+1]...^arr[j-1] ,也就是a，同理可得b
代码如下：

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        int[] xor = new int[n];
        xor[0] = arr[0];
        for(int i=1; i<n; i++) {
            xor[i] = xor[i-1] ^ arr[i];
        } //arr[0 - i]
        int ans = 0,a,b;
        for(int i = 0; i < n; i++) {
            for(int j=i+1; j < n; j++) {
                for(int k = j; k < n; k++) {
                    if(i==0) { //xor数组应该多开一位避免特判的，忘了...orz
                        a = xor[j-1];
                    } else {
                        a = xor[j-1] ^ xor[i-1]; 
                    }
                    b = xor[k] ^ xor[j-1];
                    if(a==b) ans++;
                }
            }
        }
        return ans;
    }
}

抄大佬的100%题解：

 public int countTriplets(int[] arr) {
        //所有可能的组合
        int total = 0;
        int length = arr.length;
        //判断数组从i到j的元素异或结果是否是0
        for (int i = 0; i < length - 1; i++) {
            int xor = arr[i];
            for (int j = i + 1; j < length; j++) {
                xor ^= arr[j];
                //如果数组从i到j的异或结果是0，那么他们
                //可能的组合就是j-i
                if (xor == 0) {
                    total += (j - i);
                }
            }
        }
        return total;
    }