LeetCode 题解工作台
找出强数对的最大异或值 I
给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ： |x - y| 你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（ XOR ）值是在该数组所有强数对中的 最大值 。 返回数组 nums 所有可能…
5
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以枚举数组中的每一个数对 $(x, y)$，如果满足 $|x - y| \leq \min(x, y)$，那么这个数对就是一个强数对，我们可以计算这个数对的异或值，并更新答案。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
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 = [5,6,25,30]
输出：7
解释：数组 nums 中有 6 个强数对：(5, 5), (5, 6), (6, 6), (25, 25), (25, 30) 和 (30, 30) 。
这些强数对中的最大异或值是 25 XOR 30 = 7 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 5 XOR 6 = 3 。
提示：
1 <= nums.length <= 501 <= nums[i] <= 100
解题思路
方法一：枚举
我们可以枚举数组中的每一个数对 ，如果满足 ，那么这个数对就是一个强数对，我们可以计算这个数对的异或值，并更新答案。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def maximumStrongPairXor(self, nums: List[int]) -> int:
return max(x ^ y for x in nums for y in nums if abs(x - y) <= min(x, y))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) for brute-force and O(n*m) for hash lookup approaches, where n is array length and m is the number of strong pair candidates. Space complexity is O(n) for storing elements in a hash set. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate attempts nested loops without pruning.
- question_mark
Candidate considers bitwise operations to optimize XOR checks.
- question_mark
Candidate correctly uses hash set to avoid duplicate pair computations.
常见陷阱
外企场景- error
Failing to include all identical number pairs as strong pairs.
- error
Overlooking the maximum XOR coming from non-adjacent numbers.
- error
Misusing bitwise XOR without checking strong pair condition.
进阶变体
外企场景- arrow_right_alt
Compute the maximum XOR among strong pairs under a modified pairing condition.
- arrow_right_alt
Find the minimum XOR of all strong pairs instead of maximum.
- arrow_right_alt
Extend to arrays with larger elements and test the efficiency of hash-based pruning.