数组中最大数对和的最小值 图解题解
这道题到底在问什么
- 输入
- nums=[3,5,2,3]
- 输出
- 7 （配成 2+5、3+3,最大是 7）
- 输入
- nums=[3,5,4,2,4,6]
- 输出
- 8 （配成 2+6、3+5、4+4,最大是 8）
最优解：一步一步想明白
- 3记住口诀「排序后小配大、头尾向中间收,取数对和的最大」,下面每帧都在套它。
- 4先看主例 nums=[3,5,4,2,4,6]。排好序后,把最小和最大配一对,次小和次大配一对……左指针 l 从头、右指针 r 从尾,一起往中间收。
- 5第 1 对:把最小端 nums[0]=2 和最大端 nums[5]=6 配在一起,这一对的和是 8。
- 6这对的和 8 比之前都大,更新 ans = 8。这两端结算完(变蓝),l 进到 1、r 退到 4,继续配中间剩下的。
- 7第 2 对:把最小端 nums[1]=3 和最大端 nums[4]=5 配在一起,这一对的和是 8。
- 8这对的和 8 没超过当前 ans=8,ans 不变。这两端结算完(变蓝),l 进到 2、r 退到 3,继续配中间剩下的。
- 9第 3 对:把最小端 nums[2]=4 和最大端 nums[3]=4 配在一起,这一对的和是 8。
- 10这对的和 8 没超过当前 ans=8,ans 不变。所有数对都配完了。
- 113 对全部配完,每对的和取最大,得到 8。这就是「让最大数对和尽可能小」能达到的最优值。
- 12再看一个有重复值的 nums=[4,1,5,1,2,5]。排好序后,把最小和最大配一对,次小和次大配一对……左指针 l 从头、右指针 r 从尾,一起往中间收。
- 13第 1 对:把最小端 nums[0]=1 和最大端 nums[5]=5 配在一起,这一对的和是 6。
- 14这对的和 6 比之前都大,更新 ans = 6。这两端结算完(变蓝),l 进到 1、r 退到 4,继续配中间剩下的。
- 15第 2 对:把最小端 nums[1]=1 和最大端 nums[4]=5 配在一起,这一对的和是 6。
- 16这对的和 6 没超过当前 ans=6,ans 不变。这两端结算完(变蓝),l 进到 2、r 退到 3,继续配中间剩下的。
- 17第 3 对:把最小端 nums[2]=2 和最大端 nums[3]=4 配在一起,这一对的和是 6。
- 18这对的和 6 没超过当前 ans=6,ans 不变。所有数对都配完了。
- 193 对全部配完,每对的和取最大,得到 6。这就是「让最大数对和尽可能小」能达到的最优值。
- 20最后用 nums=[9,1,8,2] 快速复习一遍。排好序后,把最小和最大配一对,次小和次大配一对……左指针 l 从头、右指针 r 从尾,一起往中间收。
- 21第 1 对:把最小端 nums[0]=1 和最大端 nums[3]=9 配在一起,这一对的和是 10。
- 22这对的和 10 比之前都大,更新 ans = 10。这两端结算完(变蓝),l 进到 1、r 退到 2,继续配中间剩下的。
- 23第 2 对:把最小端 nums[1]=2 和最大端 nums[2]=8 配在一起,这一对的和是 10。
- 24这对的和 10 没超过当前 ans=10,ans 不变。所有数对都配完了。
- 252 对全部配完,每对的和取最大,得到 10。这就是「让最大数对和尽可能小」能达到的最优值。
⚠️ 容易写错的地方
✗ 错：忘记先排序就直接头尾配
✓ 对：必须先 sort,贪心结论建立在有序之上
没排序的头尾不是真正的最小和最大,配出来不是最优
✗ 错：把目标当成「最小化数对和的总和」
✓ 对：本题最小化的是最大那一对的和,不是总和
不管怎么配,所有数的总和固定,总和无法被优化;能优化的是「最大那一对」
✗ 错：循环边界写成 i ≤ n/2 多算一对
✓ 对：i 从 0 到 n/2 - 1,恰好 n/2 对
每对用掉两个数,n 个数正好 n/2 对,多走一步会重复或越界
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def minPairSum(self, nums: List[int]) -> int:
nums.sort()
return max(nums[i] + nums[~i] for i in range(len(nums)//2))C++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int minPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0, n = nums.size();
for (int i = 0; i < n / 2; ++i) ans = max(ans, nums[i] + nums[n-1-i]);
return ans;
}
};Java
import java.util.*;
class Solution {
public int minPairSum(int[] nums) {
Arrays.sort(nums);
int ans = 0, n = nums.length;
for (int i = 0; i < n / 2; i++) ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
return ans;
}
}复杂度
时间
O(n log n)
瓶颈在排序;配对只是一遍线性扫
空间
O(1) ~ O(n)
配对扫描本身 O(1) 额外空间;若把排序实现计入,空间依语言/排序实现而定,通常 O(log n) 到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组中最大数对和的最小值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么证明「小配大」一定最优?+
用交换论证。假设某个最优配法里,最大数 b 没有和最小数 a 配对:这两个数所在的两对为 (a,c)、(d,b),其中 a 是全局最小、b 是全局最大,所以 a≤d、c≤b 一定成立。这两对里较大的和是 d+b。现在把它们交换成 (a,b) 和 (c,d):因为 a≤d 得 a+b≤d+b,因为 c≤b 得 c+d≤d+b,所以新的最大和不超过原最大和 d+b。也就是说让最小陪最大不会让最大对变大。反复做这种交换,直到变成完全有序的「小配大」,最大数对和一路不增,所以有序配对最优。
这题为什么是排序而不是用堆或双指针滑窗?+
因为最优配对结构完全由「有序后头尾对应」决定,排一次序就把关系定死了,无需动态维护。双指针只是排序后遍历配对的实现手段,本质开销在 O(n log n) 的排序。堆在这里没有额外收益。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组中最大数对和的最小值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。