1877. 數組中最大數對和的最小值

思路

每次要選兩個數字配對，把所有數字配完之後，選出和最大的那一組，
現在要盡量讓和最大的這一組越小越好。

那麼對於一個數組中最大的數字來說，它應該要跟最小的數字配對，這樣才能盡量讓它的和小。

每次都選最大與最小的數字合併，並在過程中取最大值，就是答案。
因此先排序數組，用雙指針雙向遍歷，紀錄答案。

程式碼

排序 + 雙指針

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        int res = 0, left = 0, right = n - 1;
        while(left < right) {
            res = max(res, nums[left] + nums[right]);
            left++;
            right--;
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$，主要在排序。
• 空間複雜度：$O(1)$，只有用到幾個變數。