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

难度: Medium

一个数对 (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⁵

Submission

运行时间: 256 ms

内存: 25.7 MB

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        ans = nums[0] + nums[-1]
        i = 0
        j = len(nums)-1
        while i < j:
            ans = max(ans, nums[i]+nums[j])
            i += 1
            j -= 1
        return ans

Explain

为了使数对中的最大数对和最小化，可以将数组排序后，将最小的元素与最大的元素配对，第二小的元素与第二大的元素配对，以此类推。这种配对方式可以有效地将较大的数与较小的数配对，从而尽可能减小数对和的最大值。具体步骤包括：1) 对数组进行排序。2) 初始化两个指针，一个在数组的开始，一个在数组的末尾。3) 遍历数组，计算每对指针对应的数对和，并更新最大数对和。4) 返回最终的最大数对和。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()  # 对数组进行排序
        ans = nums[0] + nums[-1]  # 初始化最大数对和为第一个和最后一个元素的和
        i = 0  # 初始化左侧指针
        j = len(nums) - 1  # 初始化右侧指针
        while i < j:  # 遍历数组，更新最大数对和
            ans = max(ans, nums[i] + nums[j])  # 更新最大数对和
            i += 1  # 左侧指针右移
            j -= 1  # 右侧指针左移
        return ans  # 返回最终的最大数对和

Explore

将数组排序后配对最小和最大元素可以最小化最大数对和，主要是因为这种配对方式能有效抵消大值和小值之间的差异，从而减小每个数对和的值。例如，对于一个未排序的数组，随机配对可能导致两个大数或两个小数相配，造成数对和非常高。而排序后，从两端向中间配对，大数与相对较小的数配对，使得每个配对的和尽可能小，进而使得所有配对中的最大和也尽可能小。这种策略通过平衡每个配对来最小化最大数对和。

在这个特定的问题中，使用双指针比使用堆或散列表更为直接和高效，因为数组排序后双指针可以线性地遍历配对。使用堆或散列表虽然也可以实现配对，但其在维护顺序和执行操作时的复杂度和开销通常高于双指针。双指针方法只需要对数组进行一次排序，然后线性遍历即可，时间复杂度为O(n log n)，空间复杂度为O(1)，是解决这类问题的最优方案。

这可以通过反证法来证明。假设存在一个更优的配对方案，即存在至少一对数对和小于通过排序和双指针得到的配对方案。这意味着在更优方案中，最大的数对和必须小于排序配对方案中的最大数对和。然而，通过排序和双指针配对，我们已经将最大元素和最小元素配对，次大元素和次小元素配对，依此类推，确保每个配对的和尽可能小。任何其他配对都将导致至少一个数对的和大于或等于排序配对的最大数对和，因此不能存在更优方案，从而证明使用排序和双指针是最优的。

在所有元素都相等的数组中，此算法仍然有效且高效。因为所有元素相等，无论如何配对，每个数对和都是相同的，即任意两个相同元素之和。因此，最大数对和就是任意两个元素的和，这种情况下算法的时间复杂度主要由排序决定，为O(n log n)，但实际上可以优化为O(n)，因为当检测到所有元素相等时，可以立即返回结果。