LeetCode 1442
链接：https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/
参考：花花酱有一个非常精彩的视频讲解这道题时间复杂度不断地降低https://www.youtube.com/watch?v=30A0Z2KDvaA
方法1：前缀
时间复杂度：O(n3)
想法：异或有一些非常好的性质，比方说a ^ 0 = a, a ^ a = 0, 以及交换律。那这个题经常刷题的人肯定能想到写异或的前缀。当你求出这个前缀数组来的时候，任何一个区间内的异或值的查询就变成了O(1)，那么根据题意枚举i, j, k即可。
代码：
class Solution {
public int countTriplets(int[] arr) {
int n = arr.length;
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] ^ arr[i - 1];
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j; k < n; k++) {
if ((prefix[k + 1] ^ prefix[j]) == (prefix[j] ^ prefix[i])) {
res++;
}
}
}
}
return res;
}
}
方法2：问题转化
时间复杂度：O(n2)
想法：arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1] == arr[j] ^ arr[j + 1] ^ ... ^ arr[k]意味着arr[i] ^ arr[i + 1] ^ ... ^ arr[k] == 0，那么我只要求一些区间，它的里面的数异或起来等于0。这个题题目条件说1 <= arr[i] <= 10^8，那就是说没有0，那就是说在前缀数组prefix里面，没有连续的两个元素值相同，那就保证了当你去找到了里面值相同的元素时，你找到的这个区间长度至少是2，直接满足题目要求。因此直接求完prefix之后暴力枚举i和k即可。
class Solution {
public int countTriplets(int[] arr) {
int n = arr.length;
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] ^ arr[i - 1];
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int k = i + 1; k < n; k++) {
if (prefix[i] == prefix[k + 1]) {
res += k - i;
}
}
}
return res;
}
}
方法3：在方法2的基础上HashMap
时间复杂度：O(n)
想法：其实如果刷题比较多的话，上面这种做法求完prefix之后直接来了个暴力枚举i和k会让你觉得有些不安，因为相当于你是在找里面相同的元素，感觉用哈希表是能优化的。隐隐想起什么求子数组和为0啊或者什么其他题目。这个题果然也是可以用哈希表优化成O(n)的。我这里直接引用花花酱的讲法，假设说你遍历数组时有个类似HashMap的东西，然后对于异或的前缀prefix数组，prefix[i] == prefix[j] == prefix[k]，那你一开始遍历到j，知道前面已经有一个跟你现在异或值相同的值了，那这时候，我最终的答案要加上j - (i + 1)，那么当遍历到k的时候，k跟i直接可以选中间点，k跟j之间也可以，那会加上k * 2 - (i + 1 + j + 1)。从这里就会发现，每次我要加上的这个值跟两个东西有关：1) 前面这个异或值已经出现了多少次了. 2) 前面这些所出现的，他们的下标和是多少。因此开两个哈希表freq和sum即可。
代码：
class Solution {
public int countTriplets(int[] arr) {
int res = 0;
Map<Integer, Integer> freq = new HashMap<>();
freq.put(0, 1);
Map<Integer, Integer> sum = new HashMap<>();
int prefix = 0;
for (int i = 0; i < arr.length; i++) {
prefix ^= arr[i];
res += freq.getOrDefault(prefix, 0) * i - sum.getOrDefault(prefix, 0);
freq.merge(prefix, 1, Integer::sum);
sum.merge(prefix, i + 1, Integer::sum);
}
return res;
}
}
