力扣1442.形成两个异或相等数组的三元组数目
力扣1442.形成两个异或相等数组的三元组数目
-
同余思想
- 如果s[i-1] ^ s[k] = 0，则[i,k]区间的异或和为0
- 即s[i-1] == s[k]
- j在哪不重要，只要是[i,k]内即可
-
class Solution {public:int countTriplets(vector<int>& arr) {int n = arr.size();vector<int> s(n+1);int ans=0; for(int i=0;i<n;i++)s[i+1] = s[i] ^ arr[i];for(int i=1;i<=n;i++)for(int k=i+1;k<=n;k++)if(s[i-1] == s[k])ans += k - i;return ans;}};