Question

2588. 统计美丽子数组数目

English Version

题目描述

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：

• 选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
• 选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
• 将 nums[i] 和 nums[j] 都减去 2k 。

如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。

请你返回数组 nums 中 美丽子数组 的数目。

子数组是一个数组中一段连续 非空 的元素序列。

 

示例 1：

输入：nums = [4,3,1,2,4]
输出：2
解释：nums 中有 2 个美丽子数组：[4,_3,1,2_,4] 和 [_4,3,1,2,4_] 。
- 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
  - 选择 [_3_, 1, _2_] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。
  - 选择 [_1_, _1_, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。
- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
  - 选择 [_4_, 3, 1, 2, _4_] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] 。
  - 选择 [0, _3_, _1_, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] 。
  - 选择 [0, _2_, 0, _2_, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0] 。

示例 2：

输入：nums = [1,10,4]
输出：0
解释：nums 中没有任何美丽子数组。

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 106

解法

方法一：前缀异或 + 哈希表

我们观察发现，一个子数组能变成一个全为 $0$ 的数组，当且仅当该子数组中的所有元素，每一个二进制位上的 $1$ 的个数都是偶数个。

如果存在下标 $i$ 和 $j$，满足 $i \lt j$，且子数组 $nums[0,..,i]$ 和 $nums[0,..,j]$ 二进制位上的 $1$ 的个数同奇同偶，那么就可以将子数组 $nums[i + 1,..,j]$ 变成一个全为 $0$ 的数组。

因此，我们可以用前缀异或的方法，用哈希表 $cnt$ 统计每个前缀异或值出现的次数。遍历数组，对于每个元素 $x$，我们计算出它的前缀异或值 $mask$，然后将 $mask$ 出现的次数加到答案中。然后，我们将 $mask$ 的出现次数加 $1$。

最后，我们返回答案即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

class Solution:
  def beautifulSubarrays(self, nums: List[int]) -> int:
    cnt = Counter({0: 1})
    ans = mask = 0
    for x in nums:
      mask ^= x
      ans += cnt[mask]
      cnt[mask] += 1
    return ans

class Solution {
  public long beautifulSubarrays(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    long ans = 0;
    int mask = 0;
    for (int x : nums) {
      mask ^= x;
      ans += cnt.getOrDefault(mask, 0);
      cnt.merge(mask, 1, Integer::sum);
    }
    return ans;
  }
}

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

func beautifulSubarrays(nums []int) (ans int64) {
  cnt := map[int]int{0: 1}
  mask := 0
  for _, x := range nums {
    mask ^= x
    ans += int64(cnt[mask])
    cnt[mask]++
  }
  return
}

function beautifulSubarrays(nums: number[]): number {
  const cnt = new Map();
  cnt.set(0, 1);
  let ans = 0;
  let mask = 0;
  for (const x of nums) {
    mask ^= x;
    ans += cnt.get(mask) || 0;
    cnt.set(mask, (cnt.get(mask) || 0) + 1);
  }
  return ans;
}