561. 数组拆分 I

一、题目描述

给定长度为2n的整数数组 nums ，你的任务是将这些数分成 n 对。

例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到n 的 min(ai, bi) 总和最大。

二、解题思路

假设一个有序序列 a1 <= a2 <= a3 <= a4 ... <= an。

a1 是最小值，那它应该和谁一起组成数对呢？

由于计算总和时取的是数对中的小值 min(a1, x)，而此时 a1 是最小值，也就是说，无论 x 是哪个，实际上计算时都会被抛弃。

为了能够实现最大和，我们就选个最小和和 a1 组合，那剩下的元素里，最小的就是 a2 了，所以得到第一个数对 (a1, a2)。

以此类推，最终得到的优数对组合就是 (a1, a2), (a3, a4), ... , (an-1, an)。

而此时的最大总和就是 a1 + a3 + a5 + ... + an-1。

三、复杂度分析

• 时间 O(nlogn)
• 空间 O(1)

四、参考代码

/**
 * 数对最小值的最大和
 *
 * @param nums 数组
 * @return 最大和
 */
private int arrayPairSum(int[] nums) {
    int sum = 0;
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i += 2) {
        sum += nums[i];
    }
    return sum;
}