2588.统计美丽子数组数目

bit manipulation, hash table, prefix sum, https://leetcode.cn/problems/count-the-number-of-beautiful-subarrays/

给你一个下标从 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 <= 10^5
0 <= nums[i] <= 10^6

要解决这个问题，需要理解如何判断一个子数组是否是“美丽”的。关键在于分析每个数的二进制表示以及如何通过操作将子数组中的所有数变为零。

分析

操作的实质：
- 每次操作可以选择两个数，并且只减少它们在某些二进制位上的值。
- 这意味着，对于每个二进制位，子数组中所有数的该位的 1 的数量必须是偶数。因为每次操作可以消除两个数的该位的 1。
美丽子数组的条件：
- 如果一个子数组中，每个二进制位的 1 的数量都是偶数，那么这个子数组可以通过上述操作变为全零。
- 这可以通过 前缀异或和 来高效判断。
前缀异或和：
- 可以用一个整数 mask 来表示当前前缀中每个二进制位的奇偶性（0 表示偶数个 1，1 表示奇数个 1）。
- 如果两个前缀的 mask 相同，那么这两个前缀之间的子数组中，每个二进制位的 1 的数量一定是偶数。
哈希表优化：
- 可以用一个哈希表记录每种 mask 出现的次数。
- 遍历数组时，动态更新当前的 mask，并在哈希表中查找当前 mask 是否已经出现过。如果出现过，说明存在美丽子数组。

Python 实现：

mask_count[0] = 1 的含义是：在开始遍历数组之前，假设存在一个“空的前缀”，其 mask 值为 0。这是为了方便处理从数组起始位置开始的子数组。

python

from typing import List
from collections import defaultdict

class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        # 用于记录每种 mask 出现的次数
        mask_count = defaultdict(int)
        mask_count[0] = 1  # 初始状态，前缀为 0
        mask = 0  # 当前的 mask
        result = 0  # 美丽子数组的数量

        for num in nums:
            # 更新当前的 mask，将 num 的二进制位加入到 mask 中
            mask ^= num

            # 如果当前 mask 已经出现过，说明存在美丽子数组
            result += mask_count[mask]

            # 更新 mask_count
            mask_count[mask] += 1

        #print(mask_count)
        return result

if __name__ == "__main__":
    sol = Solution()
    print(sol.beautifulSubarrays([4, 3, 1, 2, 4]))
    #print(sol.beautifulSubarrays([1, 10, 4]))

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组，并进行常数次操作。
空间复杂度：O(2^m)，其中 m 是数组中最大数的二进制位数。在最坏情况下，哈希表可能存储所有可能的 mask。

解释

mask 的每一位表示对应二进制位的奇偶性。
如果两个位置的 mask 相同，说明这两个位置之间的子数组满足每个二进制位的 1 的数量是偶数。
哈希表记录了每种 mask 出现的次数，用于快速计算美丽子数组的数量。

这个方法高效且易于实现，适合处理大规模数据。

2588.统计美丽子数组数目 ​

2588.统计美丽子数组数目