M3514.不同XOR三元组的数目II

bit manipulation, https://leetcode.cn/problems/number-of-unique-xor-triplets-ii/

给你一个整数数组 nums 。

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

返回所有可能三元组 (i, j, k) 中不同的 XOR 值的数量。

示例 1：

输入： nums = [1,3]

输出： 2

解释：

所有可能的 XOR 三元组值为：

(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

不同的 XOR 值为 {1, 3} 。因此输出为 2 。

示例 2：

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

输出： 4

解释：

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

提示：

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

要统计所有满足 i ≤ j ≤ k 的三元组 (i,j,k) 对应的异或值

python

nums[i] ^ nums[j] ^ nums[k]

的不同结果数。注意到：

异或运算对顺序和重复都 不敏感，且 i=j=k（取同一个元素三次）以及 i<j<k（取三不同元素）都合法。因此从“值”的角度看，就是取数组中任意 3 个（可重复）元素 x,y,z，计算
```
x ^ y ^ z
```
的不同结果数。
虽然 nums.length 最多 1500，但数值本身都在 [1,1500] 范围内，所以任何三元组异或结果都落在$ [0, 2^{11}-1] = [0,2047]$ 里。我们可以利用这一点，将问题降为：
数组中元素的取值范围是 [1, 1500]，而异或操作 ^ 的结果最大不会超过 所有可能输入值的二进制位数所能表示的最大值。我们来详细解释一下：
1. 先枚举所有可能的 两元组 异或 s = x ^ y，并用一个布尔数组 pairPossible[s] 标记哪些 s 是可行的。
  - 这里允许 x=y，对应 i=j 的情况。
  - 时间：最多执行约 1500²≈2.25M 次异或，完全可行。
2. 再枚举所有可行的 s，对数组中每个值 z，令 u = s ^ z，标记 resPossible[u] = True。
  - 这样就枚举了所有 x^y^z。这一步最多 2048×1500≈3.1M 次异或，也足够快。
3. 最后数一数 resPossible 中 True 的个数，即为答案。

python

from typing import List

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        # 1. 去重取 unique 值（重复值对异或集合不影响）
        uniq = list(set(nums))
        # 2. 预计异或结果最大到 2047（1500 < 2^11）
        MAXV = 1 << 11  # =2048
        
        # 3. 标记所有可能的 x^y
        pairPossible = [False] * MAXV
        for x in uniq:
            for y in uniq:
                pairPossible[x ^ y] = True
        
        # 4. 对每个可行的 s=x^y 和每个 z，标记 s^z
        resPossible = [False] * MAXV
        for s in range(MAXV):
            if not pairPossible[s]:
                continue
            for z in uniq:
                resPossible[s ^ z] = True
        
        # 5. 统计不同的异或结果
        return sum(resPossible)

复杂度

时间：O(U² + M·U)，其中 U≤1500（不同数值个数），M=2048，约 5 百万次异或操作，Python 下轻松在几百毫秒内完成。
空间：O(M)=O(1)，用两个大小为 2048 的布尔数组。

M3514.不同XOR三元组的数目II ​

M3514.不同XOR三元组的数目II