LeetCode 1442. 形成两个异或相等数组的三元组数目（周赛）

题目描述

1442. 形成两个异或相等数组的三元组数目

解法：（C++）

详细参考 java_Lee

其实这道题有个超好理解的地方，如果 $a==b$，那么 $a?b=0$，这样我们就超好找到能满足条件的子区间了。

对于累加 $a[1]+a[2]+...a[9]=0$ 等价于 $sum(9)?sum(0)$（存在$a[0]$），即 $a[i]+a[i+1]+...+a[k]=0$，只需要 $sum(k)==?sum(i?1)$

记累积异或的结果为 $xxor$，如果 $xxor(i?1)=xxor(k)$，那么$arr[i]???arr[k]=0$

于是，就可以用一个哈希表来记录累积异或值相同时的下标了，然后对于三元组$(i,j,k)$， $j$ 可以取遍 $i+1,?,k$ 共 $k?i$种情况

至于在取 $j$ 的所有情况的时候，我们采用了前 n 项和的思想取缔了一层嵌套循环

for(int i=0;i<indx.size()-1;i++)
{
    int start = indx[i]+1;for(int j=i+1;j<=indx.size()-1;j++)ans += indx[j]-start;
}

对于三元组$(i,j,k)$，记录的起始下标是 $i?1$， 而 $j$ 总共是 $k?i$ 种情况，所以 int start = indx[i]+1;

改进后，时间复杂度可以从 $O(n^2)$ 降到 $O(n)$

vector<int> ssum(indx);
for(int i=1;i<ssum.size();i++)ssum[i] += ssum[i-1];
int n = ssum.size()-1;
for(int i=0;i<n;i++)ans += ssum[n]-ssum[i]-(n-i)*(indx[i]+1);

最后是完整的代码

class Solution {
    
public:int countTriplets(vector<int>& arr) {
    unordered_map<int, vector<int>> table;table[0] = {
    -1};int xxor = 0;for(int i=0;i<arr.size();i++)table[(xxor^=arr[i])].push_back(i);int ans = 0;for(auto item: table){
    vector<int>& indx = item.second;vector<int> ssum(indx);for(int i=1;i<ssum.size();i++)ssum[i] += ssum[i-1];int n = ssum.size()-1;for(int i=0;i<n;i++)ans += ssum[n]-ssum[i]-(n-i)*(indx[i]+1);}return ans;}
};