本题出自http://LeetCode2588，题目主要考察了哈希表以及异或运算
题目
给你一个下标从 0 开始的整数数组
nums。每次操作中，你可以：
- 选择两个满足
0 <= i, j < nums.length的不同下标i和j。- 选择一个非负整数
k，满足nums[i]和nums[j]在二进制下的第k位（下标编号从 0 开始）是1。- 将
nums[i]和nums[j]都减去2k。如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为
0的数组，那么我们称它是一个 美丽 的子数组。请你返回数组
nums中 美丽子数组 的数目。子数组是一个数组中一段连续 非空 的元素序列。
示例
输入：nums = [1,10,4] 输出：0 解释：nums 中没有任何美丽子数组。
输入：nums = [4,3,1,2,4] 输出：2 解释：nums 中有 2 个美丽子数组：[4,3,1,2,4] 和 [4,3,1,2,4] 。 - 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：- 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。- 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。 - 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：- 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0]
题解
解题思路
题目要求寻找美丽子数组的数量。美丽子数组的定义是经过特定操作后能全变为0的连续子数组。操作的核心在于成对消除二进制位上的1。因此，子数组每一位的1的总数必须为偶数。这等价于子数组的异或结果为0。利用前缀异或数组，问题转化为寻找异或前缀相同的两个位置，从而形成异或总和为0的子数组。
解题过程
前缀异或与哈希表
使用前缀异或数组xor，其中xor[i]表示前i个元素的异或结果。若xor[j] == xor[i-1]，则子数组i到j的异或总和为0。实时统计与更新
遍历数组，维护当前前缀异或值s和哈希表cnt记录每个异或值的出现次数。初始时，哈希表存入{0:1}，处理从第一个元素开始的子数组。累加答案
每遇到一个元素，更新当前异或值s。若s已在哈希表中，则当前子数组可与之前所有相同异或值的子数组组合，答案累加对应次数。最后更新哈希表中s的计数。
代码实现
class Solution {public long beautifulSubarrays(int[] nums) {Map<Integer, Integer> cnt = new HashMap<>();int s = 0;long ans = 0;cnt.put(0, 1); // 初始化，处理前缀异或为0的子数组for (int x : nums) {s ^= x; // 更新当前前缀异或值ans += cnt.getOrDefault(s, 0); // 累加符合条件的子数组数目cnt.put(s, cnt.getOrDefault(s, 0) + 1); // 更新哈希表}return ans;}
}总结
关键思路
将美丽子数组的条件转化为异或结果为0，利用前缀异或和哈希表高效统计符合条件的子数组数目。知识点
位运算（异或操作的性质）
前缀和/前缀异或思想
哈希表优化统计
易错点
忘记初始化哈希表为
{0:1}，导致漏算以首元素开头的子数组。未正确理解操作与异或结果的关系，导致条件分析错误。
重难点
问题转化为异或前缀相等的判断。
哈希表的动态维护与实时统计。
