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

1. 整体思路

核心问题

我们需要将一个长度为偶数的数组 nums 中的元素两两配对，使得所有数对和中的最大值尽可能小。

算法逻辑：贪心策略

1. 直觉：
   • 为了让数对和的最大值尽可能小，我们需要避免'大数 + 大数'的情况（这会产生极大的和）。
   • 最好的策略是让最大的数去中和最小的数。
   • 也就是：第 1 小 + 第 1 大，第 2 小 + 第 2 大，…，第 k 小 + 第 k 大。
   • 这种'首尾配对'的策略可以平均化每对的和，从而压低最大值的上界。
2. 具体步骤：
   • 排序：首先对数组进行升序排序。
   • 双指针/首尾遍历：使用一个循环，同时取数组最左边（较小）和最右边（较大）的元素进行求和。
   • 更新最大值：在遍历过程中，记录下所有配对和中的最大值。

2. 完整代码

import java.util.Arrays;

class Solution {
    public int minPairSum(int[] nums) {
        // 1. 排序
        // 将数组按从小到大排序，以便使用贪心策略
        // 排序是本算法最耗时的步骤
        Arrays.sort(nums);
        int n = nums.length;
        int max = 0; // 记录遍历过程中的最大数对和
        
        // 2. 首尾配对遍历
        // 只需要遍历前半部分 (0 到 n/2 - 1)
        // 第 i 个元素 (较小值) 与 第 n-1-i 个元素 (较大值) 配对
        for (int i = 0; i < n / 2; i++) {
            int left = nums[i]; // 当前这一对中的最小值
            int right = nums[n - i - 1]; // 当前这一对中的最大值
            
            // 计算当前对的和，并尝试更新全局最大值
            // 我们希望最小化这个 max
            max = Math.max(left + right, max);
        }
        
        // 返回记录到的最大数对和
        return max;
    }
}

3. 时空复杂度

假设数组 nums 的长度为 N。

时间复杂度：O(N \log N)

• 排序：Arrays.sort 使用双轴快速排序，平均时间复杂度为 O(N \log N)。这是算法的主导部分。
• 遍历：单次循环遍历数组的一半，复杂度为 O(N)。
• 总计：O(N \log N) + O(N) = O(N \log N)。

空间复杂度：O(log N)

• 计算依据：
  • 代码本身只使用了常数个额外变量 (n, max, left, right)。
  • 但是，Java 的 Arrays.sort 对于基本数据类型 int 使用的是 Dual-Pivot Quicksort。虽然它是原地排序（in-place），但递归调用栈需要消耗 O(log N) 的空间。
• 结论：O(log N)。