Medium

题目描述

给定一个整数数组 nums。

异或三元组定义为三个元素的异或运算 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。

返回所有可能三元组 (i, j, k) 的唯一异或三元组值的数量。

示例 1：

输入：nums = [1,3]
输出：2
解释：
可能的异或三元组值有：
(0, 0, 0) → 1 XOR 1 XOR 1 = 1
(0, 0, 1) → 1 XOR 1 XOR 3 = 3
(0, 1, 1) → 1 XOR 3 XOR 3 = 1
(1, 1, 1) → 3 XOR 3 XOR 3 = 3

唯一的异或值是 {1, 3}。因此，输出是 2。

示例 2：

输入：nums = [6,7,8,9]
输出：4
解释：
可能的异或三元组值是 {6, 7, 8, 9}。因此，输出是 4。

约束条件：

  • 1 <= nums.length <= 1500
  • 1 <= nums[i] <= 1500

提示：

  • 任何三元组可达到的最大异或值是多少？
  • 对于每个索引 i，考虑所有索引对 (j, k) 使得 i <= j <= k。对于每一对，计算三元组异或为 nums[i] XOR nums[j] XOR nums[k]。
  • 可以通过预计算或重用中间异或结果来优化计算。

解题思路

这道题需要计算所有满足 i <= j <= k 的三元组的异或值，并统计唯一值的数量。

基础思路： 最直接的方法是三重循环枚举所有满足条件的三元组，计算异或值并用集合去重。时间复杂度为 O(n³)。

优化思路： 可以固定第一个元素 nums[i]，然后枚举后续的所有二元组 (j, k)，利用异或的性质进行优化：

  • 固定 i，对于 j >= i 和 k >= j，计算 nums[i] XOR nums[j] XOR nums[k]
  • 可以先计算 nums[j] XOR nums[k]，再与 nums[i] 异或

进一步优化： 预计算所有可能的二元组异或值，然后对每个第一个元素进行异或操作。

由于数组长度最大为1500，三重循环的复杂度在可接受范围内，我们采用最直观的解法确保正确性。使用哈希集合存储所有唯一的异或值。

代码实现

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        unordered_set<int> uniqueXors;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int k = j; k < n; k++) {
                    int xorValue = nums[i] ^ nums[j] ^ nums[k];
                    uniqueXors.insert(xorValue);
                }
            }
        }
        
        return uniqueXors.size();
    }
};

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        unique_xors = set()
        n = len(nums)
        
        for i in range(n):
            for j in range(i, n):
                for k in range(j, n):
                    xor_value = nums[i] ^ nums[j] ^ nums[k]
                    unique_xors.add(xor_value)
        
        return len(unique_xors)

public class Solution {
    public int UniqueXorTriplets(int[] nums) {
        HashSet<int> uniqueXors = new HashSet<int>();
        int n = nums.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int k = j; k < n; k++) {
                    int xorValue = nums[i] ^ nums[j] ^ nums[k];
                    uniqueXors.Add(xorValue);
                }
            }
        }
        
        return uniqueXors.Count;
    }
}

var uniqueXorTriplets = function(nums) {
    const uniqueXors = new Set();
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            for (let k = j; k < n; k++) {
                const xorValue = nums[i] ^ nums[j] ^ nums[k];
                uniqueXors.add(xorValue);
            }
        }
    }
    
    return uniqueXors.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³) - 三重循环遍历所有满足条件的三元组
空间复杂度O(min(n³, max_value)) - 哈希集合存储唯一异或值，最多有n³个三元组，但异或值受限于数组元素的最大值