LeetCode 题解工作台
找出强数对的最大异或值 II
给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ： |x - y| 你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（ XOR ）值是在该数组所有强数对中的 最大值 。 返回数组 nums 所有可能…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
观察不等式 $|x - y| \leq \min(x, y)$，其中涉及到绝对值以及最小值，我们不妨假设 $x \leq y$，则有 $y - x \leq x$，即 $y \leq 2x$。我们可以从小到大枚举 ，那么 必须满足不等式 $y \leq 2x$。 因此，我们对数组 进行排序，然后从小到大枚举 ，利用双指针维护一个窗口，使得窗口内的元素 满足不等式 $y \leq 2x$。我们…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：
|x - y| <= min(x, y)
你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。
返回数组 nums 所有可能的强数对中的 最大 异或值。
注意，你可以选择同一个整数两次来形成一个强数对。
示例 1：
输入：nums = [1,2,3,4,5]
输出：7
解释：数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。
示例 2：
输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。
示例 3：
输入：nums = [500,520,2500,3000]
输出：1020
解释：数组 nums 中有 6 个强数对：(500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000) 。
这些强数对中的最大异或值是 500 XOR 520 = 1020 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 2500 XOR 3000 = 636 。
提示：
1 <= nums.length <= 5 * 1041 <= nums[i] <= 220 - 1
解题思路
方法一：排序 + 0-1 字典树
观察不等式 ，其中涉及到绝对值以及最小值，我们不妨假设 ，则有 ，即 。我们可以从小到大枚举 ，那么 必须满足不等式 。
因此，我们对数组 进行排序，然后从小到大枚举 ，利用双指针维护一个窗口，使得窗口内的元素 满足不等式 。我们可以使用 0-1 字典树来维护窗口内的元素，这样我们就可以在 的时间内找到窗口内的最大异或值。每一次我们将 加入到字典树中，同时将窗口左端点不满足不等式的元素移除，这样就可以保证窗口内的元素满足不等式 。然后从字典树中查询最大异或值，更新答案。
时间复杂度 ，空间复杂度 。其中 是数组 的长度，而 是数组 中的最大值，本题中 。
class Trie:
__slots__ = ("children", "cnt")
def __init__(self):
self.children: List[Trie | None] = [None, None]
self.cnt = 0
def insert(self, x: int):
node = self
for i in range(20, -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: int) -> int:
node = self
ans = 0
for i in range(20, -1, -1):
v = x >> i & 1
if node.children[v ^ 1] and node.children[v ^ 1].cnt:
ans |= 1 << i
node = node.children[v ^ 1]
else:
node = node.children[v]
return ans
def remove(self, x: int):
node = self
for i in range(20, -1, -1):
v = x >> i & 1
node = node.children[v]
node.cnt -= 1
class Solution:
def maximumStrongPairXor(self, nums: List[int]) -> int:
nums.sort()
tree = Trie()
ans = i = 0
for y in nums:
tree.insert(y)
while y > nums[i] * 2:
tree.remove(nums[i])
i += 1
ans = max(ans, tree.search(y))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(n log n) for sorting plus O(n log(max_num)) for Trie traversal. Space complexity depends on the hash table or Trie size, proportional to n or max number of bits. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask why a naive double loop is too slow for n up to 5 * 10^4.
- question_mark
Probe understanding of bitwise XOR maximization using Trie structures.
- question_mark
Check if candidate strong pairs are correctly filtered before computing XORs.
常见陷阱
外企场景- error
Assuming all pairs are strong without applying the numeric condition.
- error
Using brute-force nested loops, leading to timeouts on large arrays.
- error
Failing to maintain proper hash or Trie updates when scanning the array.
进阶变体
外企场景- arrow_right_alt
Compute the minimum XOR of all strong pairs instead of maximum.
- arrow_right_alt
Find the maximum XOR among strong pairs with additional constraints on indices.
- arrow_right_alt
Adapt the problem to allow dynamic insertion of new numbers into nums and maintain maximum XOR efficiently.