LeetCode 题解工作台
统计异或值在范围内的数对有多少
给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数： low 和 high ，请返回 漂亮数对 的数目。 漂亮数对 是一个形如 (i, j) 的数对，其中 0 且 low 。 示例 1： 输入： nums = [1,4,2,7], low = 2, high = 6 输出： 6 解…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·结合·位运算·操作
答案摘要
对于这种区间 $[low, high]$ 统计的问题，我们可以考虑将其转换为统计 $[0, high]$ 和 $[0, low - 1]$ 的问题，然后相减即可得到答案。 在这道题中，我们可以统计有多少数对的异或值小于 ，然后再统计有多少数对的异或值小于 ，相减的结果就是异或值在区间 $[low, high]$ 之间的数对数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·位运算·操作 题型思路
题目描述
给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。
漂亮数对 是一个形如 (i, j) 的数对，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。
示例 1：
输入：nums = [1,4,2,7], low = 2, high = 6
输出：6
解释：所有漂亮数对 (i, j) 列出如下：
- (0, 1): nums[0] XOR nums[1] = 5
- (0, 2): nums[0] XOR nums[2] = 3
- (0, 3): nums[0] XOR nums[3] = 6
- (1, 2): nums[1] XOR nums[2] = 6
- (1, 3): nums[1] XOR nums[3] = 3
- (2, 3): nums[2] XOR nums[3] = 5
示例 2：
输入：nums = [9,8,4,2,1], low = 5, high = 14 输出：8 解释：所有漂亮数对 (i, j) 列出如下： - (0, 2): nums[0] XOR nums[2] = 13 - (0, 3): nums[0] XOR nums[3] = 11 - (0, 4): nums[0] XOR nums[4] = 8 - (1, 2): nums[1] XOR nums[2] = 12 - (1, 3): nums[1] XOR nums[3] = 10 - (1, 4): nums[1] XOR nums[4] = 9 - (2, 3): nums[2] XOR nums[3] = 6 - (2, 4): nums[2] XOR nums[4] = 5
提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 2 * 1041 <= low <= high <= 2 * 104
解题思路
方法一：0-1 字典树
对于这种区间 统计的问题，我们可以考虑将其转换为统计 和 的问题，然后相减即可得到答案。
在这道题中，我们可以统计有多少数对的异或值小于 ，然后再统计有多少数对的异或值小于 ，相减的结果就是异或值在区间 之间的数对数量。
另外，对于数组异或计数问题，我们通常可以使用“0-1 字典树”来解决。
字典树的节点定义如下：
children[0]和children[1]分别表示当前节点的左右子节点；cnt表示以当前节点为结尾的数的数量。
在字典树中，我们还定义了以下两个函数：
其中一个函数是 ，表示将数 插入到字典树中。该函数将数字 按照二进制位从高到低的顺序，插入到“0-1 字典树”中。如果当前二进制位为 ，则插入到左子节点，否则插入到右子节点。然后将节点的计数值 加 。
另一个函数是 ，表示在字典树中查找与 异或值小于 的数量。该函数从字典树的根节点 node 开始，遍历 的二进制位，从高到低，记当前 的二进制位的数为 。如果当前 的二进制位为 ，此时我们可以直接将答案加上与 的当前二进制位 相同的子节点的计数值 ，然后将当前节点移动到与 的当前二进制位 不同的子节点，即 node = node.children[v ^ 1]。继续遍历下一位。如果当前 的二进制位为 ，此时我们只能将当前节点移动到与 的当前二进制位 相同的子节点，即 node = node.children[v]。继续遍历下一位。遍历完 的二进制位后，返回答案。
有了以上两个函数，我们就可以解决本题了。
我们遍历数组 nums，对于每个数 ，我们先在字典树中查找与 异或值小于 的数量，然后在字典树中查找与 异或值小于 的数对数量，将两者的差值加到答案中。接着将 插入到字典树中。继续遍历下一个数 ，直到遍历完数组 nums。最后返回答案即可。
时间复杂度 ，空间复杂度 。其中 为数组 nums 的长度，而 为数组 nums 中的最大值。本题中我们直接取 。
class Trie:
def __init__(self):
self.children = [None] * 2
self.cnt = 0
def insert(self, x):
node = self
for i in range(15, -1, -1):
v = x >> i & 1
if node.children[v] is None:
node.children[v] = Trie()
node = node.children[v]
node.cnt += 1
def search(self, x, limit):
node = self
ans = 0
for i in range(15, -1, -1):
if node is None:
return ans
v = x >> i & 1
if limit >> i & 1:
if node.children[v]:
ans += node.children[v].cnt
node = node.children[v ^ 1]
else:
node = node.children[v]
return ans
class Solution:
def countPairs(self, nums: List[int], low: int, high: int) -> int:
ans = 0
tree = Trie()
for x in nums:
ans += tree.search(x, high + 1) - tree.search(x, low)
tree.insert(x)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * log M), where M is the maximum number representable in nums (up to 2*10^4), since each trie operation traverses at most log M bits. Space complexity is O(n * log M) for storing the trie nodes corresponding to prefix XORs. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Notice the problem can be reduced to counting pairs with XOR ≤ K.
- question_mark
Trie usage hints at bit manipulation optimization over brute-force pair checks.
- question_mark
Be careful with edge cases where low equals high or duplicates exist in the array.
常见陷阱
外企场景- error
Attempting O(n^2) brute-force pair enumeration results in TLE for large arrays.
- error
Failing to subtract pairs < low from pairs ≤ high leads to incorrect counts.
- error
Not handling bits properly in the trie, especially for leading zeros, can cause undercounting.
进阶变体
外企场景- arrow_right_alt
Count pairs with XOR exactly equal to K instead of a range.
- arrow_right_alt
Find the maximum XOR obtainable from any pair in the array.
- arrow_right_alt
Count triplets where XOR of three numbers lies in a given range.