image.png
/**
* @param {number[]} arr
* @return {number}
*/
var countTriplets = function(arr) {
const n = arr.length;
const s = [0];
for (const num of arr) {
s.push(s[s.length - 1] ^ num);
}
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j; k < n; k++) {
if (s[i] === s[k + 1]) {
ans++;
}
}
}
}
return ans;
};
这道题本身没有什么难点，主要是梳理下异或的特殊性
定义长度为 n 的数组 arr 的异或前缀和有以下关系
Si = arr[0] ^ arr[1] ^ ...... ^ arr[i-1] 1<=i<=n
由上式可得
Si = Si-1 ^ a[i-1]
继续演化
Si ^ Sj = ( arr[0] ^ arr[1] ^ ...... ^ arr[i-1] ) ^ ( arr[0] ^ arr[1] ^ ...... ^ arr[j-1] )
继续演化
Si ^ Sj = arr[i] ^ .... ^ arr[j-1] (和加减法不分先后顺序一样，异或其实是同理的)
由以上推论可得数组 arr 的子区间 [i,j] 的元素异或和为可表示为
Si ^ Sj+1
则题干中的a,b可简化为
a = Si ^ Sj
b = Sj ^ Sk+1
因此a === b 简化为
Si ^ Sj === Sj ^ Sk+1
最终结论
Si === Sk+1
