1877.数组中最大数对和的最小值：排序

【LetMeFly】1877.数组中最大数对和的最小值：排序

力扣题目链接：https://leetcode.cn/problems/minimize-maximum-pair-sum-in-array/

一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。

• 比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。

给你一个长度为 偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：

• nums 中每个元素 恰好 在 一个 数对中，且
• 最大数对和 的值 最小 。

请你在最优数对划分的方案下，返回最小的 最大数对和 。

 

示例 1：

输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。

示例 2：

输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。

 

提示：

• n == nums.length
• 2 <= n <= 105
• n 是 偶数 。
• 1 <= nums[i] <= 105

解题方法：排序

试想，对于最小的元素$a$，要和哪个元素组成一对呢？当然是要和最大的元素$b$组成一对。

否则，最大的元素$b$就要和比$a$可能更大的$c$组成一对，和肯定要更大（或持平）。

处理完最小元素$a$和最大元素$b$，剩下元素也同理，每次将剩下的最小元素和最大元素配对即可。

这种不限制远近任意组合成对的题目，排序是不会影响顺序的。我们可以对nums排个序。

• 时间复杂度$O(n\log n)$
• 空间复杂度$O(\log n)$

AC代码

C++

/*
 * @LastEditTime: 2026-01-24 09:30:46
 */
class Solution {
public:
    int minPairSum(vector<int>& nums) {
        int ans = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() / 2; i++) {
            ans = max(ans, nums[i] + nums[nums.size() - i - 1]);
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2026-01-24 09:36:17
'''
from typing import List

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return max(nums[i] + nums[~i] for i in range(len(nums) // 2))

Java

/*
 * @LastEditTime: 2026-01-24 09:39:41
 */
import java.util.Arrays;

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < nums.length / 2; i++) {
            ans = Math.max(ans, nums[i] + nums[nums.length - i - 1]);
        }
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2026-01-24 09:34:40
 */
package main

import "sort"

func minPairSum(nums []int) (ans int) {
    sort.Ints(nums)
    for i := 0; i < len(nums) / 2; i++ {
        ans = max(ans, nums[i] + nums[len(nums) - i - 1])
    }
    return
}

Rust

/*
 * @LastEditTime: 2026-01-24 09:37:33
 */
impl Solution {
    pub fn min_pair_sum(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let mut ans = 0;
        for i in 0..nums.len() / 2 {
            ans = ans.max(nums[i] + nums[nums.len() - i - 1]);
        }
        ans
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源