一道非常经典的前缀异或题

今天刷到一道题，可谓是将异或的性质利用到了极致

请看题

解这道题我们需要用到异或的两个性质

1. x*x = 0
2. 0^x = x;

所以要求数组中下标i到j的异或为
arr[i]^……arr[j]=(arr[0]^……arr[i-1]) ^ (arr[0]^……arr[i-1]) ^ (arr[i]^……arr[j]);
即:原式=(arr[0]^……^arr[i-1]) ^ (arr[0]^…………^arr[j])；
假设：前缀和数组xors。xors[i+1]表示arr[0]^……arr[i]。那么易知题中的a = xors[i]^xors[j]。b = xors[j]^xors[k+1]。当a==b时，xors[i]==xors[k+1]。且对于j>i&&j<=k均成立。所以我们只要定k然后找i即可。

代码如下

class Solution {
public:int countTriplets(vector<int>& arr) {/*主要用到异或运算的特点：相同的数异或得0，任何数字与0异或都得到它本身*/int n = arr.size();if(n<2)return 0;vector<int> xors(n+1, 0);for(int i=0;i<n;i++){xors[i+1] = xors[i]^arr[i];}/*xors[i]^xors[j]==xors[j]^xors[k+1],约去xors[j]。所以我们只需要找到xors[i]==xors[k+1]即可，又因为j再i和k之间可以有k-i个可能值，所以每次确定一个i和k，ans就加k-i*/int ans = 0;for(int k=1;k<n;k++){for(int i=0;i<k;i++){if(xors[i]==xors[k+1]){ans+=(k-i);}}}return ans;}
};

这个代码时间复杂度为O(n^2)。
但是由于我们定k的时候下标为0到k-1的元素我们已经遍历过了。所以我们可以用哈希表存储起来。就省去了重复遍历去找i了。而且我们可以将求前缀和的过程与找三元组的过程合并起来

优化到极致的代码

class Solution {
public:int countTriplets(vector<int>& arr) {int n = arr.size();if(n<2)return 0;int ans = 0;unordered_map<int,int>cnt, total;cnt[0] = 1;total[0] = 0;int pre = arr[0], cur;for(int k=1;k<n;k++){cur = pre^arr[k];if(cnt.count(cur)>0){ans+=(cnt[cur]*k-total[cur]);}total[pre]+=k;cnt[pre]++;pre = cur;}return ans;}
};

又是收获满满的一天，加油小陈！！！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！