LeetCode 1442
鏈接：https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/
參考：花花醬有一個(gè)非常精彩的視頻講解這道題時(shí)間復(fù)雜度不斷地降低https://www.youtube.com/watch?v=30A0Z2KDvaA
方法1：前綴
時(shí)間復(fù)雜度：O(n3)
想法：異或有一些非常好的性質(zhì)澎现，比方說(shuō)a ^ 0 = a, a ^ a = 0, 以及交換律湾笛。那這個(gè)題經(jīng)常刷題的人肯定能想到寫異或的前綴揩徊。當(dāng)你求出這個(gè)前綴數(shù)組來(lái)的時(shí)候，任何一個(gè)區(qū)間內(nèi)的異或值的查詢就變成了O(1)，那么根據(jù)題意枚舉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：?jiǎn)栴}轉(zhuǎn)化
時(shí)間復(fù)雜度：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，那么我只要求一些區(qū)間紫岩，它的里面的數(shù)異或起來(lái)等于0。這個(gè)題題目條件說(shuō)1 <= arr[i] <= 10^8睬塌，那就是說(shuō)沒有0泉蝌，那就是說(shuō)在前綴數(shù)組prefix里面歇万，沒有連續(xù)的兩個(gè)元素值相同，那就保證了當(dāng)你去找到了里面值相同的元素時(shí)梨与，你找到的這個(gè)區(qū)間長(zhǎng)度至少是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的基礎(chǔ)上HashMap
時(shí)間復(fù)雜度：O(n)
想法：其實(shí)如果刷題比較多的話缘挽，上面這種做法求完prefix之后直接來(lái)了個(gè)暴力枚舉i和k會(huì)讓你覺得有些不安，因?yàn)橄喈?dāng)于你是在找里面相同的元素呻粹，感覺用哈希表是能優(yōu)化的壕曼。隱隱想起什么求子數(shù)組和為0啊或者什么其他題目。這個(gè)題果然也是可以用哈希表優(yōu)化成O(n)的等浊。我這里直接引用花花醬的講法腮郊，假設(shè)說(shuō)你遍歷數(shù)組時(shí)有個(gè)類似HashMap的東西，然后對(duì)于異或的前綴prefix數(shù)組筹燕，prefix[i] == prefix[j] == prefix[k]轧飞，那你一開始遍歷到j(luò)，知道前面已經(jīng)有一個(gè)跟你現(xiàn)在異或值相同的值了，那這時(shí)候，我最終的答案要加上j - (i + 1)迹卢，那么當(dāng)遍歷到k的時(shí)候滑臊，k跟i直接可以選中間點(diǎn)腻窒，k跟j之間也可以，那會(huì)加上k * 2 - (i + 1 + j + 1)。從這里就會(huì)發(fā)現(xiàn)，每次我要加上的這個(gè)值跟兩個(gè)東西有關(guān)：1) 前面這個(gè)異或值已經(jīng)出現(xiàn)了多少次了. 2) 前面這些所出現(xiàn)的衔掸，他們的下標(biāo)和是多少。因此開兩個(gè)哈希表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;
}
}
