1877. Minimize Maximum Pair Sum in Array

這題看題目看了一下...xd

minimized maximum pair sum

這裡的 minimized 通常都是指, 均攤, 也就是 pair sum 盡量接近

題目是要在所有湊出的 pair 數字, 取最大的

但再取 pair 時, 希望能取盡可能小的 pair, 最後再從中取出最大和的 pair

pair 的數字當然不能重複取用！

ex:

[3,5,2,3]

(2,3)5, 8(3,5) => 像這樣就是取到最大的pair 和 8

(3,3)6, 7(2,5) => 這個就比較小的 pair, 所以答案是 7

所以其實就是如何取到數字和都比較平均的方式

那就是 sort, 頭尾相加會最平均摟

so [3,5,2,3] => 2 3 3 5 => 頭尾相加, 2+5 = 7, 3+3 = 6

max(7,6) = 7

T : O(nlogn)

S: O(1)

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int res = Integer.MIN_VALUE;
        
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            res = Math.max(res, nums[left] + nums[right]);
            left++;
            right--;
        }
        return res;
    }
}

/*
[3,5,2,3]

2 3 3 5 => sort

5 8

6 7


[3,5,4,2,4,6]

2 3 4 4 5 6 => sort

2 6

3 5
 
4 4
*/