LeetCode 题解工作台
数组中的最大数对和
给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，且这两个数数位上最大的数字相等。 返回最大和，如果不存在满足题意的数字对，返回 -1 。 示例 1： 输入： nums = [51,71,17,24,42] 输出： 88 解释： i = 1 和 j = 2 …
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们先初始化答案变量 $ans = -1$。接下来，直接枚举所有的数对 $(nums[i], nums[j])$，其中 $i \lt j$，并计算它们的和 $v = nums[i] + nums[j]$。如果 比 更大，并且 和 的最大数字相同，那么我们就用 更新 。 时间复杂度 $O(n^2 \times \log M)$，其中 是数组的长度，而 是数组中的最大值。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，且这两个数数位上最大的数字相等。
返回最大和，如果不存在满足题意的数字对，返回 -1 。
示例 1：
输入：nums = [51,71,17,24,42] 输出：88 解释： i = 1 和 j = 2 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 71 + 17 = 88 。 i = 3 和 j = 4 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 24 + 42 = 66 。 可以证明不存在其他数对满足数位上最大的数字相等，所以答案是 88 。
示例 2：
输入：nums = [1,2,3,4] 输出：-1 解释：不存在数对满足数位上最大的数字相等。
提示：
2 <= nums.length <= 1001 <= nums[i] <= 104
解题思路
方法一：枚举
我们先初始化答案变量 。接下来，直接枚举所有的数对 ，其中 ，并计算它们的和 。如果 比 更大，并且 和 的最大数字相同，那么我们就用 更新 。
时间复杂度 ，其中 是数组的长度，而 是数组中的最大值。
class Solution:
def maxSum(self, nums: List[int]) -> int:
ans = -1
for i, x in enumerate(nums):
for y in nums[i + 1 :]:
v = x + y
if ans < v and max(str(x)) == max(str(y)):
ans = v
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for scanning nums and computing largest digits, plus O(1) for maintaining top two per digit since digits range 1-9. Space complexity is O(n) for the hash table mapping digits to number lists. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check that your largest digit calculation handles multiple digits correctly.
- question_mark
Ask about how to efficiently track the two largest numbers per digit without sorting every time.
- question_mark
Clarify behavior when no two numbers share the same largest digit.
常见陷阱
外企场景- error
Forgetting to update both largest and second largest numbers when scanning a digit's group.
- error
Mixing up largest digit extraction, leading to incorrect pairings.
- error
Returning zero or incorrect sum when no valid pair exists instead of -1.
进阶变体
外企场景- arrow_right_alt
Compute the maximum product of a pair sharing the same largest digit instead of the sum.
- arrow_right_alt
Return all pairs with the maximum sum that share the same largest digit.
- arrow_right_alt
Allow numbers with the same largest digit but from different arrays.