E.位运算-异或：2588. 统计美丽子数组数目

题目链接：2588. 统计美丽子数组数目（中等）

算法原理：

解法：位运算-前缀异或

题述操作中，将数减去2的k次幂，用二进制来表示的话，3-2的0次幂等同于：

0011-0001=0010，如果再-2呢，就是0010-0010=0000，可以看到，每次操作都能够让这个数的某个二进制位上的1变成0

对于两个数，就是让两个数的第k位同时变成0，那么要满足让子数组全变成0，就必须满足子数组中所有数的每一位上1的个数都是偶数

换而言之，“美丽子数组”就是这个子数组中所有数异或在一起，结果为0

为了方便取出每一个区间的异或值，我们可以借助“异或消消乐”的原理，构造出一个前缀异或数组，xor[i]表示前 i 个数的异或结果

为了避免空数组，枚举的时候 i 从0开始，j 就要从 i+1 开始，而不是从 i 开始了

但是这个双重的for循环的时间复杂度是O(N²)，在此题会引起超时，因此我们需要做出优化

优化

55ms击败39.72%

时间复杂度O(N)

用哈希表记录每个前缀异或值出现的次数，遍历数组时，记当前前缀异或值为cur，那么我们只需知道前面出现过多少次cur，就说明有多少个以当前元素结尾的子数组异或值为0，累加次数即可

上述代码实现过程类似：优选算法-前缀和：29.和为K的子数组

Java代码：

class Solution { //一开始的暴力枚举，时间复杂度O(N),会超时 //2588. 统计美丽子数组数目 public long beautifulSubarrays(int[] nums) { int n=nums.length; //记录前缀异或 //xor[i]:前i个数的异或结果 int[] xor=new int[n+1]; for(int i=1;i<=n;i++) xor[i]=xor[i-1]^nums[i-1]; //枚举所有子数组 long cnt=0; for(int i=0;i<=n;i++) for(int j=i+1;j<=n;j++) if((xor[i]^xor[j])==0) cnt++; return cnt; } }

class Solution { //优化版 //2588. 统计美丽子数组数目 public long beautifulSubarrays(int[] nums) { int n=nums.length; long cnt=0; //统计异或值出现次数 Map<Integer,Integer> hash=new HashMap<>(); hash.put(0,1); //xor[i]:前i个数的异或结果 int[] xor=new int[n+1]; for(int i=1;i<=n;i++){ xor[i]=xor[i-1]^nums[i-1]; if(hash.containsKey(xor[i])) cnt+=hash.get(xor[i]); hash.merge(xor[i],1,Integer::sum); } return cnt; } }