数组拆分 图解题解

把 2n 个数配成 n 对，求较小值之和最大

给一个长度是 2n 的数组 nums，把里面的数两两分成 n 对，每一对 (a, b) 只算较小的那个 min(a, b)，再把这 n 个较小值加起来。怎么配对能让总和最大？题面给 nums=[1,4,3,2]，最好的配法是 (1,2) 和 (3,4)，较小值 1 加 3 得 4。

配对方式呈指数级，暴力算不动

要让总和最大，直觉是把所有配对方式都试一遍、挑最大的一种。可 2n 个数两两配对的方案数是 (2n−1)×(2n−3)×…×1，随 n 涨成阶乘级：8 个数就有 105 种配法，20 个数已过六亿，只能应付几个数的玩具例子，数组一大就彻底卡死。

排序后相邻配对，为什么就是最优

先把 nums 从小到大排好，再让相邻的两个数配成一对：排序后第 0 和第 1 个一对、第 2 和第 3 个一对，依此类推。每一对里左边那个，也就是下标为偶数的那个，一定不大于右边，所以它就是这对的较小值，偶数下标上的数加起来就是答案。

为什么这样配最优？先看最大的那个数，它跟谁配都是那对里较大的一个，注定拿不到分；那就让它去和紧挨着的次大数配，把次大数保下来当别人的对手。它对不对，可以用交换论证来验：假设最优配法里有个数没跟排序后的邻居配，总能找到两对、对调配对方式后总的较小值之和不会变小；反复对调就能整理成相邻配对的样子，说明它不比任何配法差。

两步走：先排序，再隔一个取一个

算法落到代码只有两步。第一步，把 nums 从小到大排序；第二步，从下标 0 出发，每隔一个取一个，也就是 0、2、4… 这些偶数位，一路加到末尾。Python 一行 sum(sorted(nums)[::2]) 就够；C++、Java 排完序用一个循环、下标每次加 2 累加。取偶数位而不是奇数位，是因为排序后每对的较小值都落在左边、也就是偶数下标那一格。

拿题面两组数据逐组核对

先走 [1,4,3,2]。排序后成 [1,2,3,4]，相邻配对是 (1,2) 和 (3,4)，取偶数下标 0 和 2 上的 1 和 3，相加得答案 4。

再走 [6,2,6,5,1,2]。排序后成 [1,2,2,5,6,6]，相邻配对 (1,2)(2,5)(6,6)，取偶数下标 0、2、4 上的 1、2、6，相加得 9。要是不排序、直接在原数组上取偶数位，拿到的是 6、6、1 加起来 13，看着更大却是错的——那三个数根本配不成三对合法的 (a, b)。

复杂度 O(n log n) 与几个容易写反的地方

整个算法的时间几乎全花在排序上，是 O(n log n)；排完之后取偶数位只是一趟线性扫描，不改变量级。额外空间只用一个累加变量，是 O(1)，排序本身的栈开销不计入。

两个写反点最常见。一是忘了排序，直接在乱序数组上取偶数位，这时偶数位并不是每对的较小值，加出来会偏大；二是排了序却取成奇数下标，拿的是每对较大值，同样偏大一截。至于只有一对、所有数相等、数组含负数这些情况，规则一律不变，排序取偶数位照样成立。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            ans += nums[i];
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < nums.length; i += 2) {
            ans += nums[i];
        }
        return ans;
    }
}