Medium

题目描述

给你一个下标从 0 开始的整数数组 nums。在一次操作中，你可以：

  • 选择两个不同的下标 i 和 j，满足 0 <= i, j < nums.length。
  • 选择一个非负整数 k，使得 nums[i] 和 nums[j] 的二进制表示中第 k 位（下标从 0 开始）都是 1。
  • 从 nums[i] 和 nums[j] 中都减去 2^k。

如果一个子数组可以通过执行上述操作任意次数（包括零次）使得其所有元素都变为 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^1。子数组变为 [1, 1, 0]。
  - 选择 [1, 1, 0] 和 k = 0。从两个数中都减去 2^0。子数组变为 [0, 0, 0]。
- 我们可以通过以下方式使子数组 [4,3,1,2,4] 中的所有元素都变为 0：
  - 选择 [4, 3, 1, 2, 4] 和 k = 2。从两个数中都减去 2^2。子数组变为 [0, 3, 1, 2, 0]。
  - 选择 [0, 3, 1, 2, 0] 和 k = 0。从两个数中都减去 2^0。子数组变为 [0, 2, 0, 2, 0]。
  - 选择 [0, 2, 0, 2, 0] 和 k = 1。从两个数中都减去 2^1。子数组变为 [0, 0, 0, 0, 0]。

示例 2：

输入：nums = [1,10,4]
输出：0
解释：nums 中没有美丽子数组。

约束条件：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^6

解题思路

这道题的关键观察是：一个子数组是美丽的当且仅当它的异或和为 0。

核心思路： 通过题目描述的操作，我们实际上是在每次操作中选择两个数的某个相同二进制位进行减法，这相当于将这两个数在该位上的 1 变为 0。要使整个子数组的所有元素都变为 0，需要每个二进制位上的 1 的个数都是偶数，这样才能完全配对消除。

这等价于子数组的异或和为 0，因为异或运算的性质就是相同位抵消。

算法步骤：

  1. 使用前缀异或的思想：如果子数组 [left, right] 的异或和为 0，那么 prefix_xor[left-1] = prefix_xor[right]
  2. 遍历数组，维护当前的前缀异或值
  3. 使用哈希表记录每个前缀异或值出现的次数
  4. 对于当前位置，查看之前是否有相同的前缀异或值，如果有，说明存在异或和为 0 的子数组

时间复杂度： O(n)，只需要遍历一次数组 空间复杂度： O(n)，哈希表最多存储 n 个不同的前缀异或值

代码实现

class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        unordered_map<int, int> count;
        count[0] = 1;  // 初始前缀异或为0
        
        int prefixXor = 0;
        long long result = 0;
        
        for (int num : nums) {
            prefixXor ^= num;
            result += count[prefixXor];
            count[prefixXor]++;
        }
        
        return result;
    }
};

class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        count = {0: 1}  # 初始前缀异或为0
        prefix_xor = 0
        result = 0
        
        for num in nums:
            prefix_xor ^= num
            result += count.get(prefix_xor, 0)
            count[prefix_xor] = count.get(prefix_xor, 0) + 1
        
        return result

public class Solution {
    public long BeautifulSubarrays(int[] nums) {
        var count = new Dictionary<int, int>();
        count[0] = 1;  // 初始前缀异或为0
        
        int prefixXor = 0;
        long result = 0;
        
        foreach (int num in nums) {
            prefixXor ^= num;
            if (count.ContainsKey(prefixXor)) {
                result += count[prefixXor];
                count[prefixXor]++;
            } else {
                count[prefixXor] = 1;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var beautifulSubarrays = function(nums) {
    const count = new Map();
    count.set(0, 1);  // 初始前缀异或为0
    
    let prefixXor = 0;
    let result = 0;
    
    for (const num of nums) {
        prefixXor ^= num;
        result += count.get(prefixXor) || 0;
        count.set(prefixXor, (count.get(prefixXor) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(n)

相关题目