2025-10-03：不同 XOR 三元组的数目Ⅱ。用go语言，给定一个整数数组 nums。枚举所有满足下标关系 i ≤ j ≤

福大大架构师每日一题

发布于 2025-12-18 13:51:05

1340

2025-10-03：不同 XOR 三元组的数目Ⅱ。用go语言，给定一个整数数组 nums。枚举所有满足下标关系 i ≤ j ≤ k 的三元组，对应的三个数做按位异或运算 nums[i] ^ nums[j] ^ nums[k]，然后统计这些异或结果中互不相同的值一共有多少，返回该数量。

1 <= nums.length <= 1500。

1 <= nums[i] <= 1500。

输入： nums = [6,7,8,9]。

输出： 4。

解释：

不同的 XOR 值为 {6, 7, 8, 9} 。因此输出为 4 。

题目来自力扣3514。

过程描述

给定一个整数数组 nums，需要统计所有满足下标关系 i ≤ j ≤ k 的三元组 (i, j, k) 的异或值 nums[i] ^ nums[j] ^ nums[k] 中不同值的数量。代码通过以下步骤实现：

1. 确定异或值的上限：
- • 首先，找到数组 nums 中的最大值，计算表示该最大值所需的最小位数 b（使用 bits.Len 函数）。
- • 设置上限 u 为 1 << b，即 2^b。这确保了所有可能的异或结果都落在范围 [0, u-1] 内，因为异或操作不会超过这个范围。
2. 预计算所有二元异或值：
- • 创建一个布尔数组 has，大小为 u，初始化为 false。该数组用于记录哪些值出现在 nums[i] ^ nums[j] 中，其中 i ≤ j。
- • 使用两层循环遍历所有 i 和 j（j 从 i 开始到数组末尾），计算每一对 (i, j) 的异或值 x ^ y（其中 x = nums[i], y = nums[j]），并将 has[x^y] 设置为 true。
3. 预计算所有三元异或值：
- • 创建另一个布尔数组 has3，大小为 u，初始化为 false。该数组用于记录所有三元组异或值。
- • 遍历 has数组中的每个值xy。如果has[xy]为true，表示xy是某个nums[i] ^ nums[j]的值，然后遍历数组中的每个元素z（即nums[k]），计算xy ^ z，并将has3[xy^z]设置为true。这一步相当于计算所有(i, j, k)的异或值，其中i ≤ j且k任意。由于异或值只取决于三个元素的值而非下标顺序，且所有i ≤ j ≤ k 的三元组都被覆盖，因此结果正确。
4. 统计不同异或值：
- • 遍历 has3 数组，统计其中为 true 的元素数量，即为所有不同异或值的数量。

复杂度分析

• 总时间复杂度：O(n²)，其中 n 是数组 nums 的长度。
- • 第一步计算最大值和上限需要 O(n) 时间。
- • 第二步预计算二元异或值需要 O(n²) 时间，因为双层循环遍历所有 i ≤ j 的组合。
- • 第三步预计算三元异或值需要 O(u * n) 时间。由于 u 是一个常数上限（最多 2048，因为 max(nums) ≤ 1500），因此这一步实际为 O(n)。
- • 总体主导项是 O(n²)。
• 总额外空间复杂度：O(1)。
- • 使用的额外空间主要是两个布尔数组 has 和 has3，大小均为 u。由于 u 是常数（最多 2048），因此空间复杂度为 O(1)。
- • 其他变量（如循环索引）占用常数空间。

Go完整代码如下：

package main

import (
    "fmt"
    "math/bits"
    "slices"
)

func uniqueXorTriplets(nums []int) (ans int) {
    u := 1 << bits.Len(uint(slices.Max(nums)))

    has := make([]bool, u)
    for i, x := range nums {
        for _, y := range nums[i:] {
            has[x^y] = true
        }
    }

    has3 := make([]bool, u)
    for xy, b := range has {
        if !b {
            continue
        }
        for _, z := range nums {
            has3[xy^z] = true
        }
    }

    for _, b := range has3 {
        if b {
            ans++
        }
    }
    return
}

func main() {
    nums := []int{6, 7, 8, 9}
    result := uniqueXorTriplets(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def unique_xor_triplets(nums):
    if not nums:
        return0

    u = 1 << (max(nums).bit_length())
    has = [False] * u
    for i, x in enumerate(nums):
        for y in nums[i:]:
            has[x ^ y] = True

    has3 = [False] * u
    for xy, b in enumerate(has):
        if not b:
            continue
        for z in nums:
            has3[xy ^ z] = True

    return sum(1for b in has3 if b)


if __name__ == "__main__":
    nums = [6, 7, 8, 9]
    result = unique_xor_triplets(nums)
    print(result)