统计美丽子数组数目

难度: Medium

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

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

如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 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 个数字都减去 2¹ ，子数组变成 [1, 1, 0] 。
  - 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 2⁰ ，子数组变成 [0, 0, 0] 。
- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
  - 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 2² ，子数组变成 [0, 3, 1, 2, 0] 。
  - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 2⁰ ，子数组变成 [0, 2, 0, 2, 0] 。
  - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 2¹ ，子数组变成 [0, 0, 0, 0, 0] 。

示例 2：

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

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶

Submission

运行时间: 133 ms

内存: 36.6 MB

class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        Map = {0:1}
        ans = 0
        num = 0
        for n in nums:
            num ^= n
            if num not in Map:
                Map[num] = 1
            else:
                ans += Map[num]
                Map[num] += 1
        return ans

Explain

本题解采用了异或和哈希表的方法来检测美丽子数组。核心思想是使用异或运算的性质：任何数与自身异或的结果为0，以及异或运算的可交换性。遍历数组，计算从第一个元素到当前元素的异或累积结果 num。如果在某个位置的异或累积结果 num 已经出现在哈希表 Map 中，说明从前一个相同异或结果的位置到当前位置的子数组异或结果为0，即这个子数组可以通过上述操作全部变为0，因此是一个美丽子数组。Map 中存储的是每个异或结果出现的次数，这样可以在找到重复的异或结果时，直接通过 Map[num] 获取到当前异或结果之前出现的次数，这些都是以当前位置结尾的美丽子数组的起始位置的候选。初始时，Map 中加入 {0:1} 来表示一个虚拟的前缀，以支持从数组开始到当前位置的异或结果就是0的情况。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        Map = {0:1}  # 初始化哈希表，考虑前缀异或为0的情况
        ans = 0  # 美丽子数组的计数器
        num = 0  # 用于计算从起始到当前元素的异或值
        for n in nums:
            num ^= n  # 更新当前的异或值
            if num in Map:
                ans += Map[num]  # 如果当前异或值已经存在，说明找到了新的美丽子数组
            Map[num] = Map.get(num, 0) + 1  # 更新哈希表
        return ans  # 返回美丽子数组的总数

Explore

在哈希表中初始化{0:1}是为了处理从数组第一个元素开始到某个点的子数组的异或结果恰好为0的情况。这种初始化意味着在没有任何元素参与异或运算时，即数组的起始位置之前，可以认为存在一个虚拟的前缀，其异或值为0，并且这种情况出现了一次。这样，当数组中从第一个元素到当前元素的异或累积结果第一次为0时，我们可以通过查找哈希表中的0来识别这个子数组，并且增加它的计数。

当异或累积结果num在哈希表Map中已经存在时，这表明从之前某个位置到当前位置的子数组的异或结果为0。Map[num]存储的是异或结果为num的次数，每次Map[num]的值即表示存在多少个子数组的起始位置可以使得从那个位置到当前位置的子数组的异或结果为0。因此，每发现一次这样的情况，就可以直接将Map[num]的值加到总的美丽子数组计数中，因为每一个这样的起始位置都对应一个符合条件的美丽子数组。

哈希表中的次数表示异或结果为某个特定值的前缀出现的次数。对于任何位置i，如果其异或结果为num，并且这个结果之前出现过，那么每个之前的出现都可以作为一个潜在的起始位置j，使得子数组[j, i]的异或结果为0。因此，这个次数实际上帮助我们追踪到达当前异或结果的所有可能的子数组的起始边界。

在这种算法中，即使nums数组中存在重复数字，也不会对算法的效率或结果产生直接影响。异或操作本身是对位的操作，不受具体数字值的影响，只与数字本身的位模式有关。因此，重复数字的存在不会改变算法的时间复杂度O(n)或空间复杂度O(k)，其中k为数组中不同异或结果的数量。重复数字的存在仅影响异或结果的序列，但不会影响算法的整体性能或输出结果。