LeetCode 2588.统计美丽子数组数目：前缀和 + 位运算(异或) + 哈希表

【LetMeFly】2588.统计美丽子数组数目：前缀和 + 位运算(异或) + 哈希表

力扣题目链接：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 <= 105
• 0 <= nums[i] <= 106

很不错的一道题。

解题方法：前缀和 + 位运算(异或) + 哈希表

二进制下：数组中每一位都出现偶数次等价于数组是美丽数组

每一位都出现偶数次？那不是说明数组中所有元素异或起来的结果为$0$吗？

任意进制下：数组中值异或结果为0等价于数组是美丽数组

类似前缀和的思想，我们使用一个变量$val$记录数组的前缀异或和。从前到后遍历数组，遍历过程中使用当前值异或val。

如果0-4的异或结果为3，0-7的异或结果也为3，就说明5-7的异或结果为0，说明5-7的子数组是美丽子数组。

我们只需要使用一个哈希表times统计每个异或结果的出现次数，再次出现val时，历史上前缀异或和为val的次数times[val]即为以当前元素为终端的美丽子数组的个数。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(len(nums))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-03-06 16:13:50* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-06 16:32:08*/
typedef long long ll;class Solution {
private:unordered_map<int, int> times;
public:ll beautifulSubarrays(vector<int>& nums) {times[0] = 1;int val = 0;ll ans = 0;for (int t : nums) {val ^= t;ans += times[val];// printf("val = %d, times[%d] = %d, ans = %d\n", val, val, times[val], ans);  //*******times[val]++;}return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-03-06 16:35:13
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-06 16:36:59
'''
from typing import List
from collections import defaultdictclass Solution:def beautifulSubarrays(self, nums: List[int]) -> int:times = defaultdict(int)times[0] = 1ans = val = 0for t in nums:val ^= tans += times[val]times[val] += 1return ans

Java

/** @Author: LetMeFly* @Date: 2025-03-06 16:38:18* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-06 16:41:02*/
import java.util.Map;
import java.util.HashMap;class Solution {public long beautifulSubarrays(int[] nums) {Map<Integer, Integer> times = new HashMap<>();times.put(0, 1);long ans = 0;int val = 0;for (int t : nums) {val ^= t;int thisTime = times.getOrDefault(val, 0);ans += thisTime;times.put(val, ++thisTime);}return ans;}
}

Golang

/** @Author: LetMeFly* @Date: 2025-03-06 16:46:23* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-03-06 16:46:39*/
package mainfunc beautifulSubarrays(nums []int) (ans int64) {times := map[int]int{0: 1}val := 0for _, t := range nums {val ^= tans += int64(times[val])times[val]++}return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源