数组中最大数对和的最小值

记住口诀「排序后小配大、头尾向中间收,取数对和的最大」,下面每帧都在套它。

先看主例 nums=[3,5,4,2,4,6]。排好序后,把最小和最大配一对,次小和次大配一对……左指针 l 从头、右指针 r 从尾,一起往中间收。

第 1 对:把最小端 nums[0]=2 和最大端 nums[5]=6 配在一起,这一对的和是 8。

这对的和 8 比之前都大,更新 ans = 8。这两端结算完(变蓝),l 进到 1、r 退到 4,继续配中间剩下的。

第 2 对:把最小端 nums[1]=3 和最大端 nums[4]=5 配在一起,这一对的和是 8。

这对的和 8 没超过当前 ans=8,ans 不变。这两端结算完(变蓝),l 进到 2、r 退到 3,继续配中间剩下的。

第 3 对:把最小端 nums[2]=4 和最大端 nums[3]=4 配在一起,这一对的和是 8。

这对的和 8 没超过当前 ans=8,ans 不变。所有数对都配完了。

3 对全部配完,每对的和取最大,得到 8。这就是「让最大数对和尽可能小」能达到的最优值。

再看一个有重复值的 nums=[4,1,5,1,2,5]。排好序后,把最小和最大配一对,次小和次大配一对……左指针 l 从头、右指针 r 从尾,一起往中间收。

第 1 对:把最小端 nums[0]=1 和最大端 nums[5]=5 配在一起,这一对的和是 6。

这对的和 6 比之前都大,更新 ans = 6。这两端结算完(变蓝),l 进到 1、r 退到 4,继续配中间剩下的。

第 2 对:把最小端 nums[1]=1 和最大端 nums[4]=5 配在一起,这一对的和是 6。

这对的和 6 没超过当前 ans=6,ans 不变。这两端结算完(变蓝),l 进到 2、r 退到 3,继续配中间剩下的。

第 3 对:把最小端 nums[2]=2 和最大端 nums[3]=4 配在一起,这一对的和是 6。

这对的和 6 没超过当前 ans=6,ans 不变。所有数对都配完了。

3 对全部配完,每对的和取最大,得到 6。这就是「让最大数对和尽可能小」能达到的最优值。

最后用 nums=[9,1,8,2] 快速复习一遍。排好序后,把最小和最大配一对,次小和次大配一对……左指针 l 从头、右指针 r 从尾,一起往中间收。

第 1 对:把最小端 nums[0]=1 和最大端 nums[3]=9 配在一起,这一对的和是 10。

这对的和 10 比之前都大,更新 ans = 10。这两端结算完(变蓝),l 进到 1、r 退到 2,继续配中间剩下的。

第 2 对:把最小端 nums[1]=2 和最大端 nums[2]=8 配在一起,这一对的和是 10。

这对的和 10 没超过当前 ans=10,ans 不变。所有数对都配完了。

2 对全部配完,每对的和取最大,得到 10。这就是「让最大数对和尽可能小」能达到的最优值。

边界先想清:两元素就是唯一一对;全相等时配法无所谓;极端大小数也靠「小配大」抵消。

面试常被追问证明:用「交换论证」说明有序后小配大不会让最大对变大。