题目描述

原题链接：2588. 统计美丽子数组数目

解题思路

本题的难点在于对于题意的解析与思路的转化。题中说的子数组中的美丽数，相当于是要求在这个子数组中所有的数进行异或运算后，得到的结果为0。（异或运算：对相同为0，相异为1，0与任何数计算该数数值保持不变）

因此，问题就转化为了找到一个一个区间内，所有的数进行异或操作后数值变为0。此时，就相当于是在求解子区间问题并找到某一区间内的结果0，而前缀和是处理子区间内数值的常用方式。

规定前缀和为异或运算后的前缀和，只要找到前缀和相同的两个位置，此时这两个位置之间的区间，异或后就一定为0。思路类似于 面试题 17.05. 字母与数字（详细解析）。

使用一个哈希表，key为前缀和，value为具有该前缀和的个数。因为是要找到所有的满足异或后为0的子区间，因此，需要的就是对相同的前缀和进行两两配对，便计算出了所有情况。同时，当出现前缀和为0时，也说明前方已经构造了异或后为1的情况，也应该加上一。

代码实现

class Solution {
public:long long beautifulSubarrays(vector& nums) {int n = nums.size();long long res = 0;// 1、获取前缀和vector s(n + 1);for(int i = 0; i < n; i++)      s[i + 1] = s[i] ^ nums[i];      // 2、构建哈希表unordered_map cnt;// 3、记录相同前缀和的对数for(int x : s) {			// 这里要从包含s[0]开始遍历，从而cnt[0]++ = 1，让后续在有效区间段内出现0时，正常加上一次情况。res += cnt[x]++;        // 每多一个相同前缀和，就会和前方的进行两两配对，因此每次都加上cnt[x]}return res;}
};

代码优化
边计算前缀和，边统计

class Solution {
public:long long beautifulSubarrays(vector& nums) {int n = nums.size();long long res = 0;int s = 0;      // s作为每次的前缀和// 注意这里是让cnt[0] = 1，因为之后的for循环是从nums[0]直接开始，所以提前就统计上出现0时，会认为出现一次目标区间，加上这次情况unordered_map cnt{{s, 1}};        for(int x : nums) {            s ^= x;res += cnt[s]++;}return res;}
};

参考文章：【套路】前缀和+哈希表（Python/Java/C++/Go）