[前缀和+hashmap]leetcode2588：统计美丽子数组数目(medium)

题目：

---

题解：

思路：本题在比赛时没思路，主要是没想到可以用异或做，也没有想到如何转变到异或，然后用经典的 hashmap 套路。

• 1）由于每次都要减去两个数的 2^k，那么所有数中 2^k 的次数之和一定是偶数。也就是说，所有数的异或和必须是 0。那么就可以使用前缀异或和来计算数组中所有元素的前缀和了。
• 2）由 1 分析可知，美丽子数组的前缀异或和为 0。因此 pre[l]^pre[r] = 0 表示原数组 a 中区间 [l,r-1] 的异或和为0，也就是美丽子数组。 pre[l]^pre[r] = 0 等价于 pre[l] = pre[r]，所以我们只用统计 pre 中相同数的对数就是美丽子数组的个数了。使用经典的两数之和套路，hashmap 先查询再计数。

---

代码如下：

using LL = long long;
class Solution {
public:
    // 思路：使用前缀异或和，由于每次都要减去两个数的 2^k，那么所有的数中 2^k 的次数之和一定是偶数。也就是说，所有数的异或和必须是 0。pre[i]=a[0^...^i-1]，使用左闭右开区间，区间[l,r)的异或和为 pre[r]^pre[l]=a[l^...^r-1]
    long long beautifulSubarrays(vector<int>& a) {
        int n=a.size();
        vector<int> pre(n+1);
        for(int i=1;i<=n;i++)pre[i]=pre[i-1]^a[i-1];
        LL res=0;
        // 使用 hashmap 来进行计数。由于只有子数组的异或和为 0，才能构成美丽子数组。所以 pre[l] ^ pre[r] = 0，那么说明 pre[l] = pre[r]，也就是说区间数组中 [l,r-1] 的异或和为 0。
        // 所以我们只用统计前缀异或和数组中相同数的对数即可，采用先查询再计数的方法。
        unordered_map<int,int> cnt;
        for(int x:pre){
            res+=cnt[x]++;
        }
        return res;
    }
};