Leetcode 1442
5.18的每日一题1442. 形成两个异或相等数组的三元组数目
a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1] b = arr[j] ^ arr[j + 1] ^ … ^ arr[k
利用了x^y = 0 ，可知两个数必相等。计算每个数的异或 ， 若出现0 ， 则说明该区间有能够令 a == b 成立的三元组 (i, j , k) 的数目
其实 i ^ k = 0 , i < j <= k , j在区间范围内，异或结果都等于0
Talk is cheap , show u the code XDDDD
public int countTriplets(int[] arr) {
int n = arr.length;
int ans = 0;
//int[] s = new int[n + 1];
//for (int i = 0; i < n; ++i) {
// s[i + 1] = s[i] ^ arr[i];
//} 官解用了[前缀异或]的方法来解答
for (int i = 0; i < n; i++) {
int sum = 0;
for (int k = i ; k < n ; k++){
sum ^= arr[k];
if (sum == 0)//if(s[i] == s[k + 1]) 即有三元区间 使得结果=0
ans += (k - i);
}
}
return ans;
}
时间复杂度：O(n)
空间复杂度：O(n)