[LeetCode] 每日一题 2588. 统计美丽子数组数目
题目链接
题目描述
给你一个下标从 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^50 <= nums[i] <= 10^6
解题思路
这道题一开始可能不太好理解，但如果转换成二进制视角，就会变得非常直观
操作解析
题目中给定的操作本质上是把两个数的某个二进制位的 1 变成 0
如果某个子数组能够通过这样的操作全部变成 0，那么它的所有数字的每一位必须都出现偶数次的 1
异或前缀和的应用
我们可以用异或运算来解决这个问题，因为异或的特性就是：
相同的数异或后变 0，即
x ^ x = 0前缀异或相同的部分会抵消
具体而言，如果前缀异或
res在两个不同位置出现了两次，说明这两个位置之间的子数组所有二进制位都是偶数个 1，符合题目要求
哈希表优化
我们使用一个哈希表
count来记录前缀异或res出现的次数：遍历
nums过程中，维护一个res表示当前前缀异或值每次查询
count[res]，即之前相同res出现的次数，这代表了多少个以当前元素结尾的美丽子数组更新
count[res]，记录当前res的出现次数
代码实现
class Solution {
public long beautifulSubarrays(int[] nums) {
HashMap<Integer, Integer> count = new HashMap<>(nums.length + 1);
long ans = 0;
int res = 0;
count.put(0, 1);
for (int num : nums) {
res ^= num;
ans += count.getOrDefault(res, 0);
count.put(res, count.getOrDefault(res, 0) + 1);
}
return ans;
}
}复杂度分析
时间复杂度：遍历
nums需要O(n)，哈希表操作的均摊复杂度是O(1)，所以总体复杂度为 O(n)空间复杂度：额外使用了哈希表存储前缀异或值，最多存储
n+1个不同值，因此 O(n)
总结
这道题的核心思路是利用异或的特性来判断子数组的二进制位是否都能变成 0：
转换成二进制思维，理解每个数的二进制位必须成对消除
使用异或前缀和，通过
res ^ res = 0来判断是否存在符合条件的子数组利用哈希表优化，存储
res出现次数，快速计算答案
这种前缀异或的思想在位运算相关的题目中经常出现，比如 "和为 K 的子数组" 这类题目，值得熟练掌握
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。