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

题目描述

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

解法：（C++）

详细参考 java_Lee

其实这道题有个超好理解的地方，如果 $a==b$，那么 $a\oplus 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]\oplus \cdots \oplus arr[k]=0$

于是，就可以用一个哈希表来记录累积异或值相同时的下标了，然后对于三元组$(i,j,k)$， $j$ 可以取遍 $i+1,\cdots ,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;
    }
};