【Leetcode 每日一题 - 补卡】2588. 统计美丽子数组数目
问题背景
给你一个下标从 0 0 0 开始的整数数组 n u m s nums nums。每次操作中，你可以：
- 选择两个满足 0 < = i , j < n u m s . l e n g t h 0 <= i, j < nums.length 0<=i,j<nums.length 的不同下标 i i i 和 j j j。
- 选择一个非负整数 k k k，满足 n u m s [ i ] nums[i] nums[i] 和 n u m s [ j ] nums[j] nums[j] 在二进制下的第 k k k 位（下标编号从 0 0 0 开始）是 1 1 1。
- 将 n u m s [ i ] nums[i] nums[i] 和 n u m s [ j ] nums[j] nums[j] 都减去 2 k 2 ^ k 2k。
如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为
0
0
0 的数组，那么我们称它是一个 美丽 的子数组。
请你返回数组
n
u
m
s
nums
nums 中 美丽子数组 的数目。
子数组是一个数组中一段连续 非空 的元素序列。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \le nums.length \le 10 ^ 5 1≤nums.length≤105
- 0 ≤ n u m s [ i ] ≤ 1 0 6 0 \le nums[i] \le 10 ^ 6 0≤nums[i]≤106
解题过程
同时减去
2
k
2 ^ k
2k 这个操作，其实就是在对应的二进制位上将
1
1
1 修改为
0
0
0。
要求若干次操作后得到全为
0
0
0 的数组，实际上需要数组中每个数的每个二进制位上
1
1
1 的数量为偶数，进一步可以转化为求异或和为零的子数组，方法类似于 和为 K 的子数组 。
需要注意，初始状态下异或和为零的次数要设置为
1
1
1，否则会漏解。
具体实现
class Solution {
public long beautifulSubarrays(int[] nums) {
long res = 0;
int xorSum = 0;
Map<Integer, Integer> count = new HashMap<>(nums.length + 1);
count.put(0, 1);
for (int num : nums) {
xorSum ^= num;
int cur = count.getOrDefault(xorSum, 0);
res += cur;
count.put(xorSum, cur + 1);
}
return res;
}
}