2588 统计美丽子数组数目

· 2025-3-6   · 次阅读   · 字数统计: 208字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

2588. 统计美丽子数组数目

分析

对于美丽子数组来说，统计其中所有数在二进制下 $1$ 的位置，每一个位置的数量均为偶数

故原问题等价于判断数组异或和是否为 $0$

又异或操作满足结合律，且任何数于其自身做异或操作为 $0$

所以我们使用前缀和来计算子数组的异或和，使用哈希表记录前缀数组异或和出现的次数

遍历计算即可

代码实现

class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        long long ans = 0;
        int t = 0;
        unordered_map<int, int> um;
        um[0] = 1;
        for(int x : nums) {
            t ^= x;
            ans += um[t]++;
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$