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

题目链接2588. 统计美丽子数组数目中等算法原理解法位运算-前缀异或题述操作中将数减去2的k次幂用二进制来表示的话3-2的0次幂等同于0011-00010010如果再-2呢就是0010-00100000可以看到每次操作都能够让这个数的某个二进制位上的1变成0对于两个数就是让两个数的第k位同时变成0那么要满足让子数组全变成0就必须满足子数组中所有数的每一位上1的个数都是偶数换而言之“美丽子数组”就是这个子数组中所有数异或在一起结果为0为了方便取出每一个区间的异或值我们可以借助“异或消消乐”的原理构造出一个前缀异或数组xor[i]表示前 i 个数的异或结果为了避免空数组枚举的时候 i 从0开始j 就要从 i1 开始而不是从 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 nnums.length; //记录前缀异或 //xor[i]:前i个数的异或结果 int[] xornew int[n1]; for(int i1;in;i) xor[i]xor[i-1]^nums[i-1]; //枚举所有子数组 long cnt0; for(int i0;in;i) for(int ji1;jn;j) if((xor[i]^xor[j])0) cnt; return cnt; } }class Solution { //优化版 //2588. 统计美丽子数组数目 public long beautifulSubarrays(int[] nums) { int nnums.length; long cnt0; //统计异或值出现次数 MapInteger,Integer hashnew HashMap(); hash.put(0,1); //xor[i]:前i个数的异或结果 int[] xornew int[n1]; for(int i1;in;i){ xor[i]xor[i-1]^nums[i-1]; if(hash.containsKey(xor[i])) cnthash.get(xor[i]); hash.merge(xor[i],1,Integer::sum); } return cnt; } }