实战：数组拆分

这道题引入了一个重要的算法思想：贪心。

贪心算法的核心是：每一步都做局部最优的选择，最终得到全局最优解。

题目描述

LeetCode 561. 数组拆分
给定长度为 2n 的整数数组 nums，你的任务是将这些数分成 n 对，例如 (a₁, b₁), (a₂, b₂), ..., (aₙ, bₙ)，使得从 1 到 n 的 min(aᵢ, bᵢ) 总和最大。
返回该最大总和。

示例 1：

输入：nums = [1, 4, 3, 2]
输出：4

解释：所有可能的分法：
1. (1, 4), (2, 3) → min(1,4) + min(2,3) = 1 + 2 = 3
2. (1, 3), (2, 4) → min(1,3) + min(2,4) = 1 + 2 = 3
3. (1, 2), (3, 4) → min(1,2) + min(3,4) = 1 + 3 = 4

所以最大总和为 4

示例 2：

输入：nums = [6, 2, 6, 5, 1, 2]
输出：9
解释：最优分法 (1, 2), (2, 5), (6, 6)，min 和为 1 + 2 + 6 = 9

题目分析

每对取 min，意味着每对中较大的数被"浪费"了——它对答案没有贡献。

为了让总和最大，我们应该让被浪费的数尽可能小。

怎么做到？

如果把数组排序，然后让相邻的两个数配对，被浪费的就是每对中稍大的那个。由于数组是排好序的，稍大的那个也只是比配对的另一个数大一点点。

这就是贪心的直觉。

贪心分析

假设排序后数组是：a₁ ≤ a₂ ≤ a₃ ≤ a₄ ≤ ... ≤ a₂ₙ

如果我们这样配对：(a₁, a₂), (a₃, a₄), ..., (a₂ₙ₋₁, a₂ₙ)

取 min 的总和是：a₁ + a₃ + a₅ + ... + a₂ₙ₋₁（所有奇数位置的数）

被浪费的是：a₂, a₄, a₆, ..., a₂ₙ（所有偶数位置的数）

为什么这样配对最优？

考虑最小的数 a₁，它一定会被取到（因为不管和谁配对，它都是 min）。

那 a₁ 应该和谁配对？如果和 a₂ₙ（最大的数）配对，a₂ₙ 就被浪费了。如果和 a₂（次小的数）配对，只浪费 a₂。显然后者更好。

对剩下的数重复这个过程，就得到了"排序后相邻配对"的策略。

解法：排序 + 取奇数位

javascript

function arrayPairSum(nums) {
    // 排序
    nums.sort((a, b) => a - b);
    
    let sum = 0;
    // 取奇数位（索引 0, 2, 4, ...）
    for (let i = 0; i < nums.length; i += 2) {
        sum += nums[i];
    }
    
    return sum;
}

执行过程

nums = [6, 2, 6, 5, 1, 2]

排序后：[1, 2, 2, 5, 6, 6]

配对：(1, 2), (2, 5), (6, 6)
        ↑       ↑       ↑
      取 1    取 2    取 6

sum = 1 + 2 + 6 = 9

复杂度分析：

时间复杂度：O(n log n)——排序的时间
空间复杂度：O(log n)——排序的递归栈空间

一个更简洁的写法

用 reduce 一行搞定：

javascript

function arrayPairSum(nums) {
    return nums.sort((a, b) => a - b)
               .reduce((sum, num, i) => i % 2 === 0 ? sum + num : sum, 0);
}

但可读性差一些，面试时还是推荐清晰的写法。

常见错误

忘记排序：直接按原顺序取会出错
取偶数位：应该取索引 0, 2, 4... 也就是排序后每对的第一个
配对理解错误：是相邻元素配对，不是首尾配对

本章小结

这一章我们学习了贪心算法的基本思想：

局部最优 → 全局最优：每一步做最好的选择
排序简化问题：很多贪心题排序后更好处理
证明正确性：贪心需要证明这样做确实最优

贪心算法不是万能的——并非所有问题都能用贪心解决。但当贪心可用时，它通常是最简洁高效的解法。

至此，第二部分"数组基础"完结。你已经掌握了数组的核心操作和常见题型。

下一部分，我们进入字符串的学习。

在 GitHub 上编辑此页

实战：数组拆分 ​

题目描述 ​

题目分析 ​

贪心分析 ​

解法：排序 + 取奇数位 ​

执行过程 ​

一个更简洁的写法 ​

常见错误 ​

相关题目 ​

本章小结 ​