给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该 最大总和 。

思路：2n长度数组，共有n对，原有思路暴力破解法，挨个遍历所有组合可能然后计算结果比较；可这里面有个问题就是组合情况很多，需要找到一个遍历所有可能的方式；

！！！取巧，发现问题结果就是尽可能保留数字大的结果，忽然发现规律，可以排序然后处理（以为自己取巧，没使用双指针等办法，结果一看示例代码和自己思路一样，哈哈）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size(); i += 2){
            sum += nums[i];
        }
        return sum;
    }
};

int main(){
    Solution s;
    // vector<int> nums = {1,4,3,2};
    vector<int> nums = {6,2,6,5,1,2};
    cout << s.arrayPairSum(nums) << endl;
    return 0;
}

额外：这题本意是双指针锻炼，进行排序，可以手撕快速排序算法；采用递归的方法调用。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void Quicksort(vector<int>& nums, int left, int right){
    int i = left, j = right;
    int pos = nums[i];
    while (i < j){
        while (i < j && nums[j] >= pos)
            j--;
        if (i < j)
            swap(nums[i++], nums[j]);
        while (i < j && nums[i] < pos)
            i++;
        if (i < j)
            swap(nums[i], nums[j--]);
    }
    if (left < i - 1)
        Quicksort(nums, left, i - 1);
    if (i + 1 < right)
        Quicksort(nums, i + 1, right);
}

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        // sort(nums.begin(), nums.end());
        Quicksort(nums, 0, nums.size() - 1);
        int pos, left = 0, right = nums.size() - 1;

        int sum = 0;
        for (int i = 0; i < nums.size(); i += 2){
            sum += nums[i];
        }
        return sum;
    }
};



int main(){
    Solution s;
    // vector<int> nums = {1,4,3,2};
    vector<int> nums = {7,3,1,0,0,6};
    cout << s.arrayPairSum(nums) << endl;
    return 0;
}