Count Triplets That Can Form Two Arrays of Equal XOR

给一个数组, 有多少组triple(i,j,k), 可以让0<= i < j<k <=n中[i,j),[j,k]的xor相等.

这题挺有意思, 直接做就是O(N^3), 是可以过的. 然后考虑优化到O(N^2), 因为xor是半加符号, 所以可以想到是用presum的方法.

首先建立pre xor数组, 但是怎么用这个数组, 可以考虑一下, xor相等的意思是值为0, 所以如果有一个区间[i,k]中的xor为0, 那么这个区间里的所有j都是答案的选项.

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length;
        int[] pre = new int[n + 1];
        for(int i = 0; i < n; i++) {
            pre[i + 1] = arr[i] ^ pre[i];
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j <= n; j++) { 
                if(pre[j] - pre[i] == 0) //(0,3) (2,5)
                    res += j - i - 1;
            }
        }
        return res;
    }
}