How do you minimize the maximum pair sum in the array?

The optimal approach is to sort the array and then use two-pointer scanning to pair the smallest and largest elements, ensuring balanced pair sums.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting step, and the two-pointer scanning takes O(n) time.

Can the solution be optimized further?

The solution is already quite efficient with O(n log n) complexity. Further optimization is unlikely unless the problem constraints change.

Why does sorting help in this problem?

Sorting allows you to pair the smallest and largest elements, minimizing the maximum sum and achieving a more balanced solution.

What pattern is used in this problem?

This problem primarily uses a two-pointer scanning technique combined with a greedy strategy and sorting to achieve optimal pairings.

#1877

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

数组中最大数对和的最小值

一个数对 (a,b) 的数对和等于 a + b 。最大数对和是一个数对数组中最大的数对和。比方说，如果我们有数对 (1,5) ， (2,3) 和 (4,4) ，最大数对和为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。给你一个长度为偶数 n 的…

数组双指针贪心排序

题目描述

一个数对 (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 <= 10⁵
n 是偶数。
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：贪心

要使得数组中最大数对和的值最小，那么我们可以将数组中最小的数和最大的数配对，次小的数和次大的数配对，依此类推。

因此，我们可以先对数组进行排序，然后使用两个指针分别指向数组的两端，求出两个指针指向的数的和，更新最大数对和的值，然后将左指针右移一位，右指针左移一位，继续进行操作，直到两个指针相遇为止，即可得到最小的最大数对和。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return max(x + nums[-i - 1] for i, x in enumerate(nums[: len(nums) >> 1]))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of the greedy pairing technique.
question_mark
Evaluate the candidate's ability to optimize through sorting.
question_mark
Check if the candidate efficiently handles larger arrays with the two-pointer approach.

warning

常见陷阱

外企场景

error
Failing to sort the array before pairing, leading to suboptimal pairings.
error
Misunderstanding the importance of balancing the pairs to minimize the maximum sum.
error
Overcomplicating the problem by attempting to pair elements randomly rather than using a structured approach.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Pairing elements with constraints on pair sums.
arrow_right_alt
Optimizing pair sums for a larger range of values.
arrow_right_alt
Extending the problem to odd-length arrays with different pairing strategies.

help

常见问题

外企场景

继续练习

#2071 你可以安排的最多任务数目 #2234 花园的最大总美丽值 #2406 将区间分为最少组数