# 1442. Count Triplets That Can Form Two Arrays of Equal XOR
###### tags: `Leetcode` `Bit Manipulation` `Medium` `HashMap`
Link: https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/
## 思路
如果$[i:j]$和$[j+1:k]$的亦或和相等，那么这个大区间$[i:k]$的亦或和就一定等于零。而这个亦或和等于零的区间$[i:k]$，你从任意位置去分成两部分，这两个子区间的亦或和又肯定是相等的。

于是这道题等价于，问有多少个区间的亦或和等于0. 对于每一个符合的区间$[i:k]$，只要令$j$为$i+1$到$k$任意一个位置，都可以满足$xor[i:j]==xor[j+1:k]$。也就是说，对于符合条件的$(i,k)$，存在$k-i$个拆分方法，得到符合条件的$(i,j,k)$。

## Code

class Solution {
    public int countTriplets(int[] arr) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        map.put(0, new ArrayList<>());
        map.get(0).add(-1);
        int res = 0;
        int xorSum = 0;
        for(int i=0; i<arr.length; i++){
            xorSum ^= arr[i];
            for(int j:map.getOrDefault(xorSum, new ArrayList<>())){
                res += Math.max(0,i-j-1);
            }
            if(!map.containsKey(xorSum)) map.put(xorSum, new ArrayList<>());
            map.get(xorSum).add(i);
        }
        return res;
    }
}