力扣2588题解：利用前缀异或和与哈希表求解美丽子数组问题

一、题目解读

力扣2588题要求计算给定数组中“美丽子数组”的数量。所谓“美丽子数组”，是指子数组的异或和为0。题目关键在于理解子数组异或和的性质，并通过高效算法统计符合条件的子数组数量。

二、解题思路

采用“前缀异或和+哈希表”的巧妙思路。核心思想是：若两个前缀异或和相同，则中间子数组的异或和必为0（因为异或满足消去律）。通过维护前缀异或和的哈希表，统计每个前缀值出现的次数，即可快速计算出符合条件的子数组数。

三、解题步骤

1. 初始化：创建哈希表记录前缀异或和出现次数，将初始值0的出现次数设为1。

2. 遍历数组：计算当前前缀异或和，若哈希表中存在该值，说明存在子数组异或和为0，累加对应次数。

3. 更新哈希表：将当前前缀异或和的出现次数+1。

4. 返回结果：累计所有符合条件的子数组数量。

四、代码与注释

class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        unordered_map<int, int> prefix_xor_counts; // 存储前缀异或和及其出现次数
        prefix_xor_counts[0] = 1; // 初始前缀异或和为0出现1次（空子数组）
        
        int current_xor = 0; // 当前前缀异或和
        long long result = 0; // 结果计数器
        
        for (int num : nums) {
            current_xor ^= num; // 计算当前前缀异或和
            result += prefix_xor_counts[current_xor]; // 若存在相同前缀异或和，累加子数组数
            prefix_xor_counts[current_xor]++; // 更新当前值的出现次数
        }
        
        return result;
    }
};

五、总结

本解法通过前缀异或和将子数组问题转化为前缀计数问题，利用哈希表实现O(n)时间复杂度。关键在于理解异或运算的消去性质，以及如何将问题拆解为前缀统计。该思路可扩展至其他涉及区间异或和的场景，是算法设计中“状态转换”的经典应用。