题目描述#

给你一个下标从 0 开始的整数数组 nums。

一次操作中，你可以：

  1. 选择两个不同下标 i 和 j，满足 0 <= i, j < nums.length。
  2. 选择一个非负整数 k，满足 nums[i] 和 nums[j] 的二进制表示中第 k 位都是 1。
  3. 将 nums[i] 和 nums[j] 都减去 2^k。

如果某个子数组经过若干次这样的操作后，可以变成一个所有元素都为 0 的数组，那么称这个子数组是美丽子数组。

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

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

特别地，如果一个子数组本身所有元素初始就是 0，它也被认为是美丽的，因为不需要执行任何操作。

知识边界#

这道题的核心并不是去模拟操作过程，而是把题目中的“成对消去”抽象成异或前缀和问题。

1. 二进制按位分析#

题目中的一次操作，本质上是在两个数的某一位上各减去一个 2^k。这意味着：

  • 每次操作都会让某一位上的 1 同时减少两个。
  • 所以对于一个子数组来说，若最终能够全部消成 0，那么它在每一位上的 1 的个数都必须是偶数。

而“每一位上 1 的个数是否为偶数”正是异或的定义特征：

  • 若一组数按位异或结果为 0，说明每一位上 1 的个数都是偶数。
  • 因此，一个子数组是美丽子数组，当且仅当这个子数组所有元素的异或和为 0。

2. 前缀异或#

和前缀和类似，前缀异或也可以快速求出任意子数组的异或值。

定义：

prefix[i] = nums[0] ^ nums[1] ^ ... ^ nums[i-1]

那么子数组 nums[l...r] 的异或和为：

prefix[r+1] ^ prefix[l]

如果一个子数组是美丽子数组，那么它的异或和必须为 0，也就是：

prefix[r+1] ^ prefix[l] = 0

等价于：

prefix[r+1] = prefix[l]

所以问题就转化为：

  • 统计有多少对前缀异或值相同。

3. 哈希表统计频次#

我们可以一边遍历数组，一边维护当前前缀异或值 xor，并用哈希表记录每个前缀异或值出现了多少次。

当当前前缀异或值为 xor 时：

  • 如果它之前出现过 cnt[xor] 次，
  • 那么说明存在 cnt[xor] 个位置，可以和当前位置组成异或和为 0 的子数组，
  • 所以直接把 cnt[xor] 加到答案里。

4. Go 中 map 的实现方式#

这题最适合使用 Go 的 map 来做频次统计。

代码中写的是：

cnt := make(map[int64]int64)

这里：

  • key 表示某个前缀异或值
  • value 表示这个前缀异或值出现的次数

虽然 xor 本身是 int，但代码将它转成了 int64 作为 key，这样写也是完全可行的，且和返回值 int64 风格统一。

Go 中常见写法：

m := make(map[int]int)
m[0] = 1
m[5]++

如果某个 key 不存在，Go 会返回对应 value 类型的零值，这在计数题里非常方便。

5. 为什么要初始化 cnt[0] = 1#

这是前缀类题目的关键细节。

初始化：

cnt[0] = 1

表示“还没有遍历任何元素时，前缀异或值 0 已经出现过一次”。

这样当某个前缀异或值本身就等于 0 时，说明从开头到当前位置这一整段子数组就是一个美丽子数组，能够被正确统计进去。

例如：

nums = [1, 2, 3]

遍历到 3 时，前缀异或为：

1 ^ 2 ^ 3 = 0

如果没有预先设置 cnt[0] = 1，那么这个从下标 0 开始的子数组就会漏掉。

6. 常见错误点#

错误一：忘记初始化 cnt[0] = 1#

这是最常见错误，会漏统计从下标 0 开始的合法子数组。

错误二：误以为要模拟操作#

题目描述给了一个具体操作过程，但真正关键是提炼出：

  • 每一位上的 1 必须成对消除
  • 等价于整个子数组异或和为 0

不需要真的去“减去 2^k”。

错误三：把“和为 0”误写成“异或为 0”#

这题要求的是按位奇偶性，不是普通加法和，所以必须用异或而不是前缀和。

思路#

先把题意转化一下。

题目允许我们每次从两个不同元素中，选中同一个二进制位上的 1，然后同时减去 2^k``。这说明对于一个子数组而言，如果它最终能变成全 0，那么它的每一个二进制位上的 1` 的总个数都必须是偶数。

而“每一位上 1 的个数都是偶数”恰好等价于“这一段子数组的异或和为 0”。

所以问题就变成：

  • 统计有多少个子数组的异或和为 0。

思路一#

使用前缀异或 + 哈希表计数。

设当前遍历到位置时的前缀异或为 xor。

如果之前某个位置的前缀异或值也等于 xor，那么这两个位置之间的子数组异或和就是 0，因此它就是一个美丽子数组。

于是我们可以：

  1. 用 xor 维护当前前缀异或值。

  2. 用 cnt 记录某个前缀异或值出现过多少次。

  3. 每遍历到一个新元素：

    • 先更新 xor
    • 当前答案增加 cnt[xor]
    • 再把 cnt[xor] 加一

正是这个思路，而且写法非常简洁。

正确性说明#

设：

  • prefix[i] 表示前 i 个元素的异或和
  • 那么子数组 nums[l...r] 的异或和为 prefix[r+1] ^ prefix[l]

当一个子数组是美丽子数组时，它必须满足异或和为 0，于是：

prefix[r+1] ^ prefix[l] = 0

推出：

prefix[r+1] = prefix[l]

所以每一对相同的前缀异或值，都唯一对应一个异或和为 0 的子数组。

哈希表统计的正是“相同前缀异或值出现的次数”，因此不会重不漏，算法正确。

时间复杂度#

  • 遍历数组一次，每次操作哈希表平均是 O(1)
  • 总时间复杂度为 O(n)

空间复杂度#

  • 哈希表最多存储 n+1 个不同前缀异或值
  • 空间复杂度为 O(n)

代码#

func beautifulSubarrays(nums []int) (ans int64) {
	cnt := make(map[int64]int64)
    cnt[0] = 1
	xor := 0
	for _, x := range nums {
		xor = xor ^ x
		ans += cnt[int64(xor)]
		cnt[int64(xor)]++
	}
	return ans
}
你的IP 获取中…