1877. Minimize Maximum Pair Sum in Array

📘 題目敘述

給定一個長度為偶數的整數陣列 nums。你需要把 nums 裡的元素兩兩配對成 n/2 組，且每個元素剛好只能被用一次。

一組 pair (a, b) 的 pair sum 定義為 a + b，所有 pairs 中最大的那個 pair sum 稱為 maximum pair sum。

請你找一種配對方式，使得 maximum pair sum 最小，並回傳這個最小值。

條件限制

• n == nums.length
• 2 <= n <= 10^5
• n 一定是偶數
• 1 <= nums[i] <= 10^5

🧠 解題思路（一）最後TLE

直覺是把最小的和最大的配在一起，避免大數相加讓最大值更大。

• 每一輪找最小值位置 ps 與最大值位置 pb
• 把這一對記下來，再從 nums 中刪掉
• 重複直到配完，再取所有 pair sum 的最大值

所有變數

• nums：原本的陣列（會一直 erase）
• small：每次選到的最小值
• big：每次選到的最大值
• ps：目前最小值的位置
• pb：目前最大值的位置
• mps：最大 pair sum
• n：陣列長度

🪜 主要流程步驟

1. 反覆配對：每次抓最小和最大

• 只要 nums.size() > 0 就配對一次
• 線性掃描找到最小值 ps 與最大值 pb
• 把這一對放進 small 與 big

2. 從 nums 刪掉這一對

• 為了避免 index 錯亂，先刪掉較大的 index 再刪較小的

3. 配對完成後，算最大的 pair sum

• 掃過所有 small[k] + big[k]，取最大值回傳

💻 程式碼實作

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        vector<int> small;
        vector<int> big;
        int ps, pb;
        while (nums.size() > 0) {
            ps = 0, pb = 0;
            for (int i = 0; i < nums.size(); i++) {
                if (nums[ps] > nums[i]) {
                    ps = i;
                }
                if (nums[pb] < nums[i]) {
                    pb = i;
                }
            }
            small.push_back(nums[ps]);
            big.push_back(nums[pb]);
            if (ps > pb) {
                nums.erase(nums.begin() + ps);
                nums.erase(nums.begin() + pb);
            } else {
                nums.erase(nums.begin() + pb);
                nums.erase(nums.begin() + ps);
            }
        }
        int mps = small[0] + big[0];
        for (int j = 0; j < small.size(); j++) {
            if (mps < small[j] + big[j]) {
                mps = small[j] + big[j];
            }
        }
        return mps;
    }
};

🧠 解題思路（二）用 sort

核心想法是把最大值和最小值配對，避免大數相加造成最大值過大。

1. 先排序 nums
2. 用雙指標：左邊最小與右邊最大配對
3. 每次更新最大配對和 ans

所有變數

• nums：題目給的整數陣列
• n：陣列長度
• l：左指標
• r：右指標
• ans：目前最大配對和

🪜 主要流程步驟

1. 先排序

• sort(nums.begin(), nums.end())

2. 雙指標配對（最小 + 最大）

• 在 while (l < r) 中計算 nums[l] + nums[r]
• ans = max(ans, nums[l] + nums[r])
• 指標往內縮：l++、r--

3. 回傳答案

• 迴圈結束後，ans 即為最小可能的最大 pair sum

💻 程式碼實作（用sort）

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int l = 0, r = n - 1;
        int ans = 0;
        while (l < r) {
            ans = max(ans, nums[l] + nums[r]);
            l++;
            r--;
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/