不绕弯子先给你结论LeetCode 1877这道题解法就一句话——把数组排个序然后“最大配最小、次大配次小”这样首尾配对所有配出来的数对和里取最大值就是答案。很多第一次做这道题的人都会愣一下为什么不是相邻配对为什么非要首尾配这个“为什么”才是整道题真正的考点也是排序双指针这个套路里最值得嚼的一口饭。这篇文章不打算抄题面直接把拆题思路、证明过程、代码实现、常见坑一次讲透。不管你是一刷 LeetCode 的新手还是准备面试前突击“排序双指针”专题的老手都可以拿这篇当参考。我会尽量说人话把“排序后为什么能最优”这件事用最直白的方式解释清楚。1. 题目到底在问什么拆解输入输出与约束1.1 题干还原与示例演练先把原题“翻译”成大白话有一个长度为偶数的数组nums比如[3, 5, 4, 2, 4, 6]。我们要把数组里的元素两两配对配成n/2个数对比如(3, 5)、(4, 4)、(2, 6)。然后计算每个数对的和358、448、268。这些数对和里的最大值叫“最大数对和”。题目要求我们找到一种配对方式让这个“最大数对和”尽可能小。拿上面这个例子来说如果配成(3, 6)、(5, 4)、(2, 4)数对和分别是 9、9、6最大值是 9。如果配成(3, 5)、(4, 4)、(2, 6)数对和分别是 8、8、8最大值是 8。如果配成(3, 4)、(5, 2)、(4, 6)数对和分别是 7、7、10最大值是 10。显然第二种配法更好答案就是 8。题目让你输出的不是配对方案只是这个最小的最大数对和。LeetCode 给的示例是这样的nums [3,5,2,3]排序后是[2,3,3,5]首尾配对得到(2,5)和(3,3)数对和分别是 7 和 6最大值是 7所以输出 7。这个例子很有迷惑性因为排序后中间两个数都是 3正好配成一对容易让人误以为“取中间两个数之和”就行。1.2 隐藏条件为什么偶数长度、正整数很关键题目明确说n是偶数这保证了每个元素都能被配对不会有一个落单。这个条件很重要因为一旦数组长度是奇数问题就变成了“有一个数必须单独处理”解法会完全不一样。另外原题数据范围里nums[i]是正整数。正整数意味着数对和永远大于 0我们不需要处理负数绝对值交叉配对那种更复杂的情况。当然后面我会提到即使数组里有负数排序首尾配对的策略依然成立只是证明时要稍微绕一下。还有一个容易被忽略的约束nums.length最大到10^5。这个量级意味着O(n^2)的暴力配对肯定超时必须用O(n log n)或O(n)的算法。而排序正好是O(n log n)完全够用。1.3 换个角度看“最小化最大值”“最小化最大值”这种说法英文叫 Minimize the Maximum是算法题里非常经典的一类目标。很多题目表面上是求一个最大值实际上是在问能不能通过某种排列或分组方式把最坏情况压到最低。生活化类比一下假设公司有 n 个人要分成两人一组合作完成任务每组的“工作量”是两个成员工作能力之和。你希望把“最累的那组”的工作量降到最小。这时候最自然的想法是什么肯定是让能力最强的人去搭配能力最弱的人而不是让两个强人凑在一起否则“最强组合”一定累死。这就是这道题的核心 intuition不要让两个“大数”待在同一对里。只要两个大数被拆开让它们分别去和小数配对那么最大数对和就能被压下去。而排序这个动作就是为了我们能够一眼看出谁大谁小。2. 为什么排序是第一步两种直觉与一种反直觉2.1 直觉一想让大数不孤单就必须让大数和小数配对假设数组里有一个元素M是全局最大值。它最终必然要和某个元素x配对形成数对和M x。我们当然希望x尽量小这样这个数对和才可能小。但是问题来了全局最小值m只有一个。如果让M和m配对了那么第二大的元素M2呢它只能和剩下元素里最小的那个配对。为了不让M2的数对和太大剩下的最小元素最好也是比较小的。顺着这个思路推下去你会发现一个规律最大的元素应该和最小的元素配第二大的应该和第二小的配以此类推。这正是排序后首尾配对。这种直觉可以用“田忌赛马”来理解如果你把数组看成两组马一组是“上等马”一组是“下等马”你希望让上等马去赢下等马同时避免上等马之间互相消耗。这里没有胜负只有“两人一组”但逻辑是一样的——别让强者扎堆。2.2 直觉二为什么我们不能简单排序后相邻配对很多人第一反应是“排序后把相邻两个配成一对”即(a1, a2)、(a3, a4)……这其实是个陷阱。为什么不行看一个反例nums [1, 2, 3, 4]。相邻配对(1,2)、(3,4)数对和是 3 和 7最大值是 7。首尾配对(1,4)、(2,3)数对和是 5 和 5最大值是 5。显然 5 比 7 好。为什么相邻配对这么差因为它把最大的两个数3 和 4放在了一起制造了一个很大的数对和。虽然相邻配对在“让每一对都比较接近”这个直觉下似乎合理但在最小化最大数对和这个目标下它完全跑偏了。这告诉我们一个道理遇到“最小化最大值”的配对问题第一优先级永远是“拆开最大的”而不是“让每一对都均匀”。2.3 反直觉点最优配对方式是“最大配最小”而不是“最大配次大”有人可能会想如果让最大的和次大的配虽然这一对的和很大但次大的不会再去和其他数配其他数对和会不会因此变小我们用不等式来反驳。假设排好序后有四个数a b c d。考虑两种配对方案方案 A(a, d)和(b, c)最大数对和是max(ad, bc)。方案 B(a, c)和(b, d)最大数对和是max(ac, bd)。因为bd ac且bd bc方案 B 的最大值至少是bd。而方案 A 呢ad可能比bd小因为a bbc也可能比bd小因为c d所以方案 A 的最大值大概率更小。把这个推理推广到 n 个数任何一对“不包含当前最大值”的配对如果其中有一个较大的数没有和较小的数配而是和另一个较大的数配了那么一定可以通过“交换配对对象”来降低整体的最大值。这就是正确的核心证明思想后面我还会详细展开。3. 排序双指针的完整解法3.1 算法流程排序、左右指针、记录最大值解法其实极简标准流程就三步对数组进行升序排序。初始化左指针i 0右指针j nums.length - 1。当i j时计算sum nums[i] nums[j]用sum更新答案的最大值然后i、j--。循环结束后答案就是所有配对中最大的那个数对和。这里有一个小细节答案初始值。因为数对和不会是负数所以可以把答案初始化为 0也可以初始化为一个很小的值比如Integer.MIN_VALUE。用 0 就够了。另一个细节是不需要额外开一个数组来存配对结果。双指针的 i 和 j 本身就是配对的索引直接计算即可。3.2 复杂度分析时间复杂度O(n log n)主要花费在排序上。双指针扫描一次是O(n)因为 i 和 j 总共移动 n/2 次每次 O(1)。空间复杂度O(1)只用了几个变量。排序如果用的是 Java 的Arrays.sort()对于基本类型数组是原地排序不占额外空间如果是对对象数组排序底层可能是 TimSort需要一些额外空间但题目nums是int[]所以可以认为 O(1)。n 10^5时n log n大约1.7 * 10^6次操作完全秒过。即使n 10^6排序也只要几十毫秒级别当然受语言和常数影响。3.3 代码实现Java / Python / C 示例我用三种最常见的语言各写一遍方便你直接抄。Java 版本class Solution { public int minPairSum(int[] nums) { Arrays.sort(nums); int ans 0; int i 0, j nums.length - 1; while (i j) { ans Math.max(ans, nums[i] nums[j]); i; j--; } return ans; } }Python 版本class Solution: def minPairSum(self, nums: List[int]) - int: nums.sort() ans 0 i, j 0, len(nums) - 1 while i j: ans max(ans, nums[i] nums[j]) i 1 j - 1 return ansC 版本class Solution { public: int minPairSum(vectorint nums) { sort(nums.begin(), nums.end()); int ans 0; int i 0, j nums.size() - 1; while (i j) { ans max(ans, nums[i] nums[j]); i; --j; } return ans; } };代码都长得一样因为这道题本身没有坑人的边界情况。注意 Java 和 C 要包含相应头文件Python 要from typing import List不过 LeetCode 环境一般已经预置了。3.4 正确性证明的思路面试要能讲出来面试时如果只背代码很可能被追问“为什么这是最优的”。所以这里把证明思路讲清楚你可以用自己的话复述。采用交换论证法Exchange Argument。假设我们已经把数组排序为a1 a2 ... an要证明存在一个最优解其中a1和an配对。如果某个最优解里a1不是和an配而是和ax配ax an同时an和ay配ay a1。那么这两个数对是(a1, ax)和(ay, an)。现在我们把配对“交叉”一下变成(a1, an)和(ax, ay)。比较这两组数对和的变化原来的两个和是S1 a1 axS2 ay an。交换后的两个和是T1 a1 anT2 ax ay。我们需要证明交换后最大值不会变大。因为S2是原来两个和中较大的an最大ay a1所以S2 S1。而交换后T1 a1 an ay an S2因为a1 ay。T2 ax ay ay an S2因为ax an。所以交换后两个和都不超过原来的最大值S2也就是说“最大数对和”没有变大。既然交换不劣那么我们可以逐步把所有“最大配最小”的对调过来最终得到一个同样优或更优的“首尾配对”方案。剩下的是归纳把a1和an这一对“拿走”后剩下的a2...a(n-1)仍然是排序数组继续用同样的推理最终得到所有首尾配对都是最优的。这个证明很经典建议记下来面试时可以直接背逻辑。4. 常见问题与排查技巧实录4.1 为什么不能只取中间两个数有读者私信问过我[1, 2, 3, 4]答案为什么不是(23)5反而是(14)5巧了这俩都是 5。但换一个数组比如[1, 2, 9, 10]中间两个数是 2 和 9和为 11正确答案是(110)和(29)最大值是 11。还是 11再换[1, 8, 9, 10]中间和是 17正确答案是(110)11和(89)17最大值 17。看起来中间和好像恰好等于答案这是一个危险的错觉。再试试[1, 2, 3, 10]中间两个数和是 5首尾配对和分别是11011、235答案是 11和中间和完全不一样。所以“取中间两个数”根本不成立。中间两个数的和只反映“较小半边里较大的两个数”而答案往往被“最大数加最小数”这一对决定。通过这个例子你也能看出答案并不是某个固定的“中间值”而是所有首尾配对和的最大值。必须把所有配对都算一遍才能确定。4.2 如果存在重复元素怎么办重复元素不影响排序和双指针。比如[2, 2, 3, 3]排序后i0,j3配对(2,3)和(2,3)答案是 5。这个结果是正确的。因为重复数字在排序数组里位置相邻首尾配对自然会把重复值分散到不同对里如果偶数个重复也可能都在同一对。有个小技巧如果数组里全是同一个数x那么所有数对和都是2x答案就是2x。排序双指针也能正确算出没什么特殊处理。4.3 Java 中 int 溢出问题题目里nums[i]最大是10^5两个相加最多2 * 10^5完全不会溢出 int。但如果你在扩展题里遇到10^9级别的数两个相加会超过Integer.MAX_VALUE约 21.47 亿这时就要用long来存储求和结果。我的习惯是只要题目没明确说“结果在 int 范围内”就先用 long 算稳一点。这道题用 int 没问题但如果你想养成好习惯可以把ans声明成long最后再转成int。4.4 双指针 vs 只扫描前一半有人会想既然首尾配对左半边每个元素肯定会和右半边某个元素配对那我是不是只遍历i从 0 到n/2-1然后直接取nums[i] nums[n-1-i]的最大值就行这个想法完全可行因为双指针的j就是n-1-i。所以代码可以改写成int ans 0; for (int i 0; i nums.length / 2; i) { ans Math.max(ans, nums[i] nums[nums.length - 1 - i]); }这里要注意下标不要写错。双指针写法更通用还能应对一些变体比如“不能重复取同一个元素”之类的场景而 for 循环写法更简洁。两种都行看你喜欢哪种风格。但有一个易错点如果i一直加到n/2就会把中间两个元素重复算一次。假设 n4当i1时j2如果循环条件是i n/2i 只能取 0 和 1那就遍历了(0,3)和(1,2)两对刚好。如果循环条件写成i n就会发生i2时j1计算了(2,1)和i1重复了。所以循环边界必须写清楚。4.5 变体如果题目要求输出配对方案怎么办LeetCode 原题只要求输出最小最大数对和不要求输出方案。但如果面试官追问或者你在练习时想输出具体配对也很简单排序后(nums[i], nums[j])就是一对按i 0...n/2-1、j n-1-i挨个输出就行。注意输出方案时不要修改原数组的“原始位置”因为排序会改变元素位置。如果你需要保留原始索引就要用“值索引”的结构排序比如 Java 里自定义一个类或者用二维数组存[value, index]。但 LeetCode 这道题只关心值不关心索引所以不用折腾。4.6 实测遇到的最大坑排序方向搞反我见过很多人在写排序时用Comparator.reverseOrder()把数组降序排了结果双指针从两头配算出答案反而更大。降序排列后首尾配对本质上是“两个最大数之一”仍然和一个较小数配其实数学上等价但很多人会搞混左右指针的移动方向。最简单粗暴的规避方式就是统一升序。升序排完左小右大清清楚楚。如果要降序那就要明白你其实是让最小的在右边逻辑容易绕晕。建议写题时保持升序别给自己添乱。5. 从这道题延伸排序对撞指针的套路5.1 什么样的题目会用到“排序对撞指针”LeetCode 里有不少题是这种套路核心特征一般是数组长度较大暴力枚举不行。要求两两配对、找两个数、或者在某种条件下求最大/最小。排序不会破坏问题的本质因为只关心值不关心原始位置。优化目标通常和“最大最小”有关。典型题目比如两数之和 II - 输入有序数组排序后左右指针找目标和。盛最多水的容器对撞指针不断移动矮的一边。救生艇排序后最大配最小尽量让一船坐两人。分发饼干排序后贪心匹配。1877 和 881 非常像都是“配对优化”问题。如果你做完 1877顺手做一下 881会发现两者的贪心思路同源先把最大的和最小组装如果放得下就一起否则最大的单独处理。5.2 与“两数之和”对比为什么 1877 要先排序“两数之和”如果数组无序通常用哈希表做到O(n)不需要排序。但 1877 不一样它要求“配对成多个数对”这个全局约束导致我们不能简单地用哈希表找某一个目标值而是要从整体上平衡所有配对。排序在这里不是可有可无的优化而是让“最大最小配对”这个贪心策略能够被直接执行的前提。所以刷题时要学会判断如果题目问“找某一对满足条件”哈希表往往更优如果问“把所有元素配对后的某种极值”排序往往是自然的思考起点。5.3 延伸练习怎么从 1877 迁移到其他题你可以试着自己变一变把“最小化最大数对和”改成“最大化最小数对和”解法会变成什么如果数组长度是奇数落单的那个数不算进任何数对和或者必须自己作为一对怎么做如果每个数对不仅看和还看两个元素的差比如最小化“最大差值”排序后该怎么做这些变体不一定都有标准答案但多想一想能加深对排序贪心的理解。我的建议是每次刷完一道题至少自己写一个变体或者看官方题解里有没有“同类题型”链接顺手点开做一两道比干刷十道重复题有效得多。最后分享一点实战心得我刷这道题的时候第一次也想成了相邻配对结果一看示例[3,5,2,3]相邻配对得到(3,5)8和(2,3)5最大值 8还以为是正确答案提交直接 WA。后来认真推导才发现只要[3,5,2,3]换一种配对(2,5)7和(3,3)6最大值是 7更好。踩过这一次坑之后我给自己定了一个规矩凡是“两两配对 最小化最大值”的题先问一句“最大的那个应该和谁配”。答案永远是“和当前最小的配”。这个思维模型救了我很多次希望也能帮到你。另外这道题表面考排序实际考的是贪心证明。建议你面试前把“交换论证”这一段自己推一遍不要只背结论。能清楚地讲出“为什么最大配最小不会让答案变差”比会写十行代码更让面试官认可。最后再补一个小技巧如果数组长度是偶数双指针循环条件写成while (i j)永远不会错如果哪天题目改成奇数记得单独处理中间那个元素。代码只有几行但边界条件花不了你一分钟检查别偷懒。