LeetCode 题解工作台
统计美丽子数组数目
给你一个下标从 0 开始的整数数组 nums 。每次操作中，你可以： 选择两个满足 0 的不同下标 i 和 j 。 选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。 将 nums[i] 和 nums[j] 都减去 2 k 。 …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们观察发现，一个子数组能变成一个全为 的数组，当且仅当该子数组中的所有元素，每一个二进制位上的 的个数都是偶数个。 如果存在下标 和 ，满足 $i \lt j$，且子数组 和 二进制位上的 的个数同奇同偶，那么就可以将子数组 $nums[i + 1,..,j]$ 变成一个全为 的数组。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
- 选择两个满足
0 <= i, j < nums.length的不同下标i和j。 - 选择一个非负整数
k，满足nums[i]和nums[j]在二进制下的第k位（下标编号从 0 开始）是1。 - 将
nums[i]和nums[j]都减去2k。
如果一个子数组内执行上述操作若干次（包括 0 次）后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。
请你返回数组 nums 中 美丽子数组 的数目。
子数组是一个数组中一段连续 非空 的元素序列。
注意：所有元素最初都是 0 的子数组被认为是美丽的，因为不需要进行任何操作。
示例 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 <= 1050 <= nums[i] <= 106
解题思路
方法一：前缀异或 + 哈希表
我们观察发现，一个子数组能变成一个全为 的数组，当且仅当该子数组中的所有元素，每一个二进制位上的 的个数都是偶数个。
如果存在下标 和 ，满足 ，且子数组 和 二进制位上的 的个数同奇同偶，那么就可以将子数组 变成一个全为 的数组。
因此，我们可以用前缀异或的方法，用哈希表 统计每个前缀异或值出现的次数。遍历数组，对于每个元素 ，我们计算出它的前缀异或值 ，然后将 出现的次数加到答案中。然后，我们将 的出现次数加 。
最后，我们返回答案即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for familiarity with XOR operations and efficient hash table use.
- question_mark
Candidates should recognize that this problem relies heavily on array scanning and hash lookups.
- question_mark
Expect to see a clear understanding of how to use cumulative XOR and hash tables to optimize the solution.
常见陷阱
外企场景- error
Forgetting to update the hash table correctly during array scanning.
- error
Overcomplicating the solution by not recognizing the XOR operation as a key part of the problem.
- error
Misunderstanding the XOR condition for beautiful subarrays, leading to incorrect subarray identification.
进阶变体
外企场景- arrow_right_alt
Modify the problem to find the number of subarrays where the XOR is equal to a given target value.
- arrow_right_alt
Extend the problem to multidimensional arrays and find beautiful subarrays in each row or column.
- arrow_right_alt
Allow negative integers in the array and adjust the solution to handle them while still using XOR.