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

Love The Way You Lie 2022-09-06 14:26 136阅读 0赞

[https://leetcode-cn.com/problems/minimize-maximum-pair-sum-in-array/][https_leetcode-cn.com_problems_minimize-maximum-pair-sum-in-array]

难度中等67

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

通过次数29,856提交次数36,427

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dldHVnbHk_size_16_color_FFFFFF_t_70][]

[https_leetcode-cn.com_problems_minimize-maximum-pair-sum-in-array]: https://leetcode-cn.com/problems/minimize-maximum-pair-sum-in-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dldHVnbHk_size_16_color_FFFFFF_t_70]: /images/20220829/c9170de6c05948e89a5b182945b7697b.png