LeetCode 561. 数组拆分
目录
题目描述
题意分析
题目目标：给长度为 $2n$ 的数组，把它拆成 $n$ 个二元组，使得所有二元组「较小值之和」最大，返回这个最大值。
核心约束：分组方式共有 $(2n-1)!!$ 种，枚举完全不可行，所以题目一定存在某种可以直接构造最优解的结构性规律。另一个信号是数组长度固定为偶数、且元素可以重复——重复值意味着「较小值」在相等时取谁都一样，不需要额外区分。
边界处理：元素可以是负数（范围 $[-10^4, 10^4]$），所以答案可能为负，累加器不能初始化成 0 之外的东西再去比较；$n = 1$ 时只有一组，答案就是两个数里的较小者；全部元素相同时答案是
n * 该值。
实现取舍：值域只有 $2 \times 10^4$ 而元素个数最多 $2 \times 10^4$，既可以用通用排序 $O(n\log n)$，也可以用计数排序做到 $O(n + C)$。面试里先给排序版本，再把计数排序当作优化说出来。
解法：排序 + 取偶数下标
核心思路
暴力做法是枚举所有配对方案，对每种方案累加
min，取最大值。方案数是双阶乘量级，$n = 10$ 就已经上亿，直接排除。
瓶颈在于我们把「配对」当成了自由组合。换个视角想想每个元素的命运：数组里的每个数要么在它所属二元组里当「较小值」被计入答案，要么当「较大值」被完全浪费。$2n$ 个数中恰好有 $n$ 个被浪费。所以目标等价于——让被浪费掉的那 $n$ 个数尽可能小，也就是让每个「浪费」都尽可能廉价。
沿着这条线做交换论证。把数组升序排好记作 $a_1 \le a_2 \le \dots \le a_{2n}$。最大的那个数 $a_{2n}$ 无论和谁配对，它自己都不会被计入（它是这一对里的较大值，除非相等，相等时计谁都一样）。既然它注定浪费，就该拿它去「消耗」掉当前剩下的第二大的数 $a_{2n-1}$——因为跟 $a_{2n}$ 配对的那个数一定被计入，选谁计入谁，当然选剩下里最大的 $a_{2n-1}$。这一步取到 $a_{2n-1}$，是这一对能贡献的上界。把这两个拿掉后，剩下 $2n-2$ 个数是同样的子问题，归纳下去即可。
于是不变量是：排序后按相邻两两配对，第 $2i$ 与第 $2i+1$ 个元素成组（0-indexed），每组贡献下标为偶数的那个。答案 $= \sum_{i=0}^{n-1} a_{2i}$。反过来也能给出上界证明：对任意配对方案，把每对的较小值从大到小排列，第 $k$ 大的较小值不可能超过排序数组中的 $a_{2n-2k+1}$，两边求和即得同一个式子，所以这个构造既可行又是上界，必为最优。
落到代码上，状态就一个：累加器
sum，含义是「已处理的若干组中较小值之和」。排序把「找较小值」这件事变成了「下标是偶数」，判断被彻底消掉。
解题步骤
第一步：对
nums升序排序。 为什么必须排序：上面的交换论证依赖「最大的和次大的配对」这条顺序关系，不排序就无法在 $O(1)$ 时间内认出谁是当前最大、谁该被牺牲。
第二步：从下标 0 开始，每次步长 2 累加
nums[i]。 为什么取偶数下标：排序后第 $2i$ 和第 $2i+1$ 个元素是一组，组内升序，所以下标小的那个（偶数下标）就是较小值。这一步把「求 min」变成了「跳着取」，是排序带来的直接红利。
第三步：返回
sum。 为什么不需要特判空数组或奇数长度：题目保证长度为 $2n$ 且 $n \ge 1$，循环自然覆盖所有组。
以
nums = [6, 2, 6, 5, 1, 2]走一遍：排序后得到[1, 2, 2, 5, 6, 6]，$n = 3$，配对方式是(1,2)、(2,5)、(6,6)。
$i = 0$：
nums[0] = 1，这一组是(1, 2)，较小值 1，sum = 1。可以对照交换论证的反向理解——最小的 1 注定要拖累与它同组的那个数，那就让它拖累尽可能小的 2，而不是让它去毁掉一个 6。
$i = 2$：
nums[2] = 2，这一组是(2, 5)，较小值 2，sum = 1 + 2 = 3。
$i = 4$：
nums[4] = 6，这一组是(6, 6)，较小值 6，sum = 3 + 6 = 9。两个 6 相等，取哪个都一样，这正是「重复值不需要特别处理」的体现。
循环结束返回 9，与期望一致。作为反例对照：如果配成
(1,6)、(2,6)、(2,5)，得到1 + 2 + 2 = 5，比 9 小得多——因为两个 6 被分别用来「浪费」了两个较大的数，而没有互相抵消。
代码实现
class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i += 2) {
sum += nums[i];
}
return sum;
}
}
func arrayPairSum(nums []int) int {
sort.Ints(nums)
sum := 0
for i := 0; i < len(nums); i += 2 {
sum += nums[i]
}
return sum
}
复杂度分析
- 时间复杂度：$O(n \log n)$。凭什么：排序是唯一的非线性开销；随后的累加只跳着扫描一遍数组，是 $O(n)$，被排序吸收。若改用计数排序（值域 $C = 2 \times 10^4 + 1$），可降到 $O(n + C)$。
- 空间复杂度：$O(\log n)$。凭什么：算法本身只有一个累加器；额外空间全部来自排序的递归栈——Java 对基本类型数组用双轴快排、Go 的
sort.Ints用内省排序，都是 $O(\log n)$ 栈深。不计排序则为 $O(1)$。
关键点总结
- 「最大化所有 min 之和」等价于「最小化被浪费的那一半」，换个目标函数往往能看见结构。 这类互补视角在配对、划分、删除类题目里反复出现。
- 交换论证的标准套路是「盯住极值元素，证明把它放在某个位置不会更差」。 本题盯的是最大值：它注定不被计入，那就让它去消耗次大值。会讲这条论证，比会写两行代码值钱得多。
- 排序的价值不只是有序，更是把「比较判断」编译成「下标算术」。 排完序之后
min消失了，只剩i += 2，代码复杂度的下降就来自这里。- 值域有限时随手评估计数排序。 元素范围与元素个数同量级时，$O(n + C)$ 严格优于 $O(n\log n)$，这是面试里可以主动加分的一句。
- 负数会让答案为负，累加器和初值都要能承载。 这类边界在「求和最大」的题里经常被忽略。
- 面试视角：这题是典型的「结论一句话、证明才是考点」。上来直接说「排序取偶数下标」会显得像背题，正确打开方式是先说明每个数只有「被计入」和「被浪费」两种命运，再给交换论证，最后补一句上界证明说明构造最优，最后才写代码并提计数排序优化。
易错点总结
- 错误写法：不排序直接取偶数下标 → 用例
[6,2,6,5,1,2]，直接取下标 0、2、4 得到6 + 6 + 1 = 13，看似更大，实则这不是任何合法配对的取 min 结果（配对(6,2)的较小值是 2 不是 6），提交后判错。- 错误写法：排序后取奇数下标
i = 1; i += 2→ 用例[1,2,2,5,6,6]得到2 + 5 + 6 = 13，取的是每组较大值，答案偏大，期望 9。- 错误写法：降序排序后仍取偶数下标 → 用例排序成
[6,6,5,2,2,1]，取下标 0、2、4 得6 + 5 + 2 = 13，同样取到了每组较大值。- 错误写法：写成
sum += Math.min(nums[i], nums[i + 1])但循环条件是i < nums.length且步长为 1 → 用例[1,2,2,5,6,6]会把(1,2)、(2,2)、(2,5)… 全部重叠地算一遍，且最后一次nums[i+1]越界抛ArrayIndexOutOfBoundsException。- 错误写法：配对方式改成「首尾相配」，即
nums[i]与nums[2n-1-i]一组 → 用例[1,2,2,5,6,6]得到min(1,6) + min(2,6) + min(2,5) = 1 + 2 + 2 = 5，远小于 9。- 错误写法：以为「相邻配对」指的是原数组中的相邻元素 → 用例
[6,2,6,5,1,2]不排序按原序相邻配对得min(6,2) + min(6,5) + min(1,2) = 2 + 5 + 1 = 8，比 9 小。- 错误写法：用
long之外的类型担心溢出而改用short/byte累加 → 用例 $n = 10^4$ 且全为 $10^4$ 时和为 $10^8$，超出short范围直接溢出成负数；int足够，不要画蛇添足。- 错误写法：认定答案非负而把
sum初始化为某个正数或最后取Math.max(sum, 0)→ 用例[-1, -2]，正确答案是 -2，被夹成 0。- 错误写法：为了「不破坏原数组」先
clone再排序却对原数组累加 → 用例[6,2,6,5,1,2]累加的是未排序的6 + 6 + 1 = 13，排序白做了。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 455. 分发饼干 | 简单 | 两个数组之间做贪心匹配，需要双指针推进而非固定步长取值 |
| 462. 最小操作次数使数组元素相等 II | 中等 | 排序后取的是中位数这一个点，靠的是绝对值和的凸性而非交换论证 |
| 881. 救生艇 | 中等 | 同样先排序再配对，但配对规则是最轻与最重相配，与本题的相邻配对正好相反 |