Easy

题目描述

给定长度为 2n 的整数数组 nums，你的任务是将这些整数分成 n 对 (a1, b1), (a2, b2), …, (an, bn)，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该最大总和。

示例 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
解释：最优分对是 (2, 1), (2, 5), (6, 6)。min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9。

约束条件：

  • 1 <= n <= 10^4
  • nums.length == 2 * n
  • -10^4 <= nums[i] <= 10^4

解题思路

解题思路

核心观察：要使所有对的最小值之和最大，我们需要让每个较小的数都尽可能大。

关键洞察：

  1. 在每一对 (a, b) 中，较小的数会被选入结果，较大的数会被"牺牲"掉
  2. 为了最大化总和，我们应该让被牺牲的数尽可能小
  3. 这意味着我们应该将相邻的数配对

算法步骤：

  1. 将数组排序
  2. 选择所有偶数索引位置的元素（即第 0, 2, 4, … 个元素）
  3. 这些元素的和就是答案

为什么这样做是最优的：

  • 排序后，每个偶数位置的元素都与其右邻居配对
  • 由于数组有序，偶数位置的元素必然是这一对中的较小值
  • 这种配对方式确保了较大的数只会牺牲掉比它小的最接近的数，从而最大化了总和

时间复杂度分析：排序需要 O(n log n)，遍历需要 O(n)，总体为 O(n log n)。

代码实现

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            sum += nums[i];
        }
        return sum;
    }
};

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

public class Solution {
    public int ArrayPairSum(int[] nums) {
        Array.Sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.Length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

var arrayPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    let sum = 0;
    for (let i = 0; i < nums.length; i += 2) {
        sum += nums[i];
    }
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n log n)
空间复杂度O(1)

相关题目