2588.统计美丽子数组数目

链接：2588.统计美丽子数组数目
难度：Medium
标签：位运算、数组、哈希表、前缀和
简介：请你返回数组 nums 中 美丽子数组 的数目。

题解 1 - cpp

• 编辑时间：2023-03-12
• 执行用时：268ms
• 内存消耗：117.5MB
• 编程语言：cpp
• 解法介绍：前缀和遍历，统计前面相同的掩码数。

class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        unordered_map<int, int> m;
        m[0]++;
        long long res = 0;
        int mask = 0;
        for (auto &num : nums) {
            mask |= num;
            res += m[mask];
            m[mask]++;
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-03-12
• 执行用时：280ms
• 内存消耗：36.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        m = Counter()
        m[0] += 1
        res, mask = 0, 0
        for num in nums:
            mask ^= num
            res += m[mask]
            m[mask] += 1
        return res

题解 3 - rust

• 编辑时间：2023-03-12
• 执行用时：36ms
• 内存消耗：4.6MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn beautiful_subarrays(nums: Vec<i32>) -> i64 {
        let mut m = std::collections::HashMap::<i32, i32>::new();
        m.insert(0, 1);
        let (mut res, mut mask) = (0i64, 0);
        for num in nums {
            mask ^= num;
            let item = m.entry(mask).or_insert(0);
            res += *item as i64;
            *item += 1;
        }
        res
    }
}