为方便计算差值，先把 $\textit{nums}$ 从小到大排序。

把 $\textit{nums}$ 中的元素画在一维数轴上。如果 $\textit{nums}[i]$ 是 $k$ 个数中的最大值，那么最小值的下标至多为 $i-k+1$（要在最小值和最大值之间再选 $k-2$ 个数）。但最小值越小，差值越大，所以最小值的下标恰好为 $i-k+1$ 是最优的。

枚举最大值的下标 $i = k-1,k,k+1,\ldots, n-1$，计算差值 $\textit{nums}[i] - \textit{nums}[i-k+1]$ 的最大值，即为答案。

class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
return min(nums[i] - nums[i - k + 1] for i in range(k - 1, n))

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(mx - mn for mx, mn in zip(nums[k - 1:], nums))

class Solution {
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
int ans = Integer.MAX_VALUE;
for (int i = k - 1; i < nums.length; i++) {
ans = Math.min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}
}

class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
ranges::sort(nums);
int ans = INT_MAX;
for (int i = k - 1; i < nums.size(); i++) {
ans = min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}
};

#define MIN(a, b) ((b) < (a) ? (b) : (a))

int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}

int minimumDifference(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), cmp);
int ans = INT_MAX;
for (int i = k - 1; i < numsSize; i++) {
ans = MIN(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}

func minimumDifference(nums []int, k int) int {
slices.Sort(nums)
ans := math.MaxInt
for i := k - 1; i < len(nums); i++ {
ans = min(ans, nums[i]-nums[i-k+1])
}
return ans
}

var minimumDifference = function(nums, k) {
nums.sort((a, b) => a - b);
let ans = Infinity;
for (let i = k - 1; i < nums.length; i++) {
ans = Math.min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
};

impl Solution {
pub fn minimum_difference(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort_unstable();
let k = k as usize;
let mut ans = i32::MAX;
for i in k - 1..nums.len() {
ans = ans.min(nums[i] - nums[i - k + 1]);
}
ans
}
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。瓶颈在排序上。
• 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。

返回可能的 最小差值 。

 

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

 

提示：

• 1 <= k <= nums.length <= 1000
• 0 <= nums[i] <= 105

排序 + 滑动窗口

从 $n$ 个元素里找 $k$ 个，使得 $k$ 个元素最大差值最小。

最大值最小化问题容易想到「二分」，利用答案本身具有「二段性」，来将原本的求解问题转化为判断定问题。

回到本题，容易证明，这 $k$ 个元素必然是有序数组中（排序后）的连续段。反证法，若最佳 $k$ 个选择不是连续段，能够调整为连续段，结果不会变差。

因此我们可以先对 $nums$ 进行排序，然后扫描所有大小为 $k$ 的窗口，直接找到答案，而无须使用「二分」。

代码（二分答案代码见 $P2$）：

###Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, ans = nums[k - 1] - nums[0];
        for (int i = k; i < n; i++) {
            ans = Math.min(ans, nums[i] - nums[i - k + 1]);
        }
        return ans;
    }
}

###Java

class Solution {
    int[] nums; int k;
    public int minimumDifference(int[] _nums, int _k) {
        nums = _nums; k = _k;
        Arrays.sort(nums);
        int l = 0, r = 100010;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
    boolean check(int x) {
        int n = nums.length, ans = nums[k - 1] - nums[0];
        for (int i = k; i < n && ans > x; i++) {
            ans = Math.min(ans, nums[i] - nums[i - k + 1]);
        }
        return ans <= x;
    }
}

• 时间复杂度：排序复杂度为 $O(n\log{n})$；遍历得到答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(\log{n})$

---

其他「滑动窗口」内容

题太简单？来看一道 更贴合笔试/面试的滑动窗口综合题 🎉 🎉

或是加练其他「滑动窗口」内容 🍭🍭🍭

题目	题解	难度	推荐指数
3. 无重复字符的最长子串	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
30. 串联所有单词的子串	LeetCode 题解链接	困难	🤩🤩
187. 重复的DNA序列	LeetCode 题解链接	中等	🤩🤩🤩🤩
219. 存在重复元素 II	LeetCode 题解链接	简单	🤩🤩🤩🤩
424. 替换后的最长重复字符	LeetCode 题解链接	中等	🤩🤩🤩🤩
438. 找到字符串中所有字母异位词	LeetCode 题解链接	中等	🤩🤩🤩🤩
480. 滑动窗口中位数	LeetCode 题解链接	困难	🤩🤩🤩🤩
567. 字符串的排列	LeetCode 题解链接	中等	🤩🤩🤩
594. 最长和谐子序列	LeetCode 题解链接	简单	🤩🤩🤩🤩
643. 子数组最大平均数 I	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
992. K 个不同整数的子数组	LeetCode 题解链接	困难	🤩🤩🤩🤩
1004. 最大连续1的个数 III	LeetCode 题解链接	中等	🤩🤩🤩
1052. 爱生气的书店老板	LeetCode 题解链接	中等	🤩🤩🤩
1208. 尽可能使字符串相等	LeetCode 题解链接	中等	🤩🤩🤩
1423. 可获得的最大点数	LeetCode 题解链接	中等	🤩🤩🤩🤩
1438. 绝对差不超过限制的最长连续子数组	LeetCode 题解链接	中等	🤩🤩🤩
1610. 可见点的最大数目	LeetCode 题解链接	困难	🤩🤩🤩🤩
1838. 最高频元素的频数	LeetCode 题解链接	中等	🤩🤩🤩
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

解题思路

排序后我们要选k个数达到最大最小的差尽可能小，必然是连续的长度为k的子数组的选法，而差值就是最右边的元素减去最左边的元素。
遍历返回其中的最小值即可。

代码

###Python3

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        return min(s[i + k - 1] - s[i] for i in range(len(s) - k + 1)) if k > 1 and (s:=sorted(nums)) else 0

###Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        if(k == 1)
            return 0;
        Arrays.sort(nums);
        int ans = 100005;
        for(int i = 0; i <= nums.length - k; i++)
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        return ans;
    }
}

###JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumDifference = function(nums, k) {
    if(k == 1)
        return 0
    nums.sort((a,b)=>a-b)
    let ans = 100005
    for(let i = 0; i <= nums.length - k; i++)
        ans = Math.min(ans, nums[i + k - 1] - nums[i])
    return ans
};

###Go

func minimumDifference(nums []int, k int) int {
    if k == 1 {
        return 0
    }
    sort.Ints(nums)
    ans := 100005
    for i := 0; i <= len(nums) - k; i++ {
        ans = min(ans, nums[i + k - 1] - nums[i])
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

方法一：排序

思路与算法

要想最小化选择的 $k$ 名学生中最高分和最低分的差值，我们一定是在排好序后的数组中连续地进行选择。这是因为在选择时，如果跳过了某个下标 $i$，那么在选择完毕后，将其中的最高分替换成 $\textit{nums}[i]$，最高分一定不会变大，与最低分的差值同样也不会变大。因此，一定存在有一种最优的选择方案，是连续选择了有序数组中的 $k$ 个连续的元素。

这样一来，我们首先对数组 $\textit{nums}$ 进行升序排序，随后使用一个大小固定为 $k$ 的滑动窗口在 $\textit{nums}$ 上进行遍历。记滑动窗口的左边界为 $i$，那么右边界即为 $i+k-1$，窗口中的 $k$ 名学生最高分和最低分的差值即为 $\textit{nums}[i+k-1] - \textit{nums}[i]$。

最终的答案即为所有 $\textit{nums}[i+k-1] - \textit{nums}[i]$ 中的最小值。

代码

###C++

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = INT_MAX;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};

###Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}

###C#

public class Solution {
    public int MinimumDifference(int[] nums, int k) {
        int n = nums.Length;
        Array.Sort(nums);
        int ans = int.MaxValue;
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = Math.Min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}

###Python

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

###C

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int cmp(const void * pa, const void *pb) {
    return *(int *)pa - *(int *)pb;
}

int minimumDifference(int* nums, int numsSize, int k){
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans = INT_MAX;
    for (int i = 0; i + k - 1 < numsSize; ++i) {
        ans = MIN(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
}

###JavaScript

var minimumDifference = function(nums, k) {
    const n = nums.length;
    nums.sort((a, b) => a - b);
    let ans = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < n - k + 1; i++) {
        ans = Math.min(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
};

###go

func minimumDifference(nums []int, k int) int {
    sort.Ints(nums)
    ans := math.MaxInt32
    for i, num := range nums[:len(nums)-k+1] {
        ans = min(ans, nums[i+k-1]-num)
    }
    return ans
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。排序需要的时间为 $O(n \log n)$，后续遍历需要的时间为 $O(n)$。

• 空间复杂度：$O(\log n)$，即为排序需要使用的栈空间。

一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。

• 比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。

给你一个长度为 偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：

• nums 中每个元素 恰好 在 一个 数对中，且
• 最大数对和 的值 最小 。

请你在最优数对划分的方案下，返回最小的 最大数对和 。

 

示例 1：

输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。

示例 2：

输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。

 

提示：

• n == nums.length
• 2 <= n <= 105
• n 是 偶数 。
• 1 <= nums[i] <= 105

基本分析 & 证明

直觉上，我们会认为「尽量让“较小数”和“较大数”组成数对，可以有效避免出现“较大数成对”的现象」。

我们来证明一下该猜想是否成立。

假定 $nums$ 本身有序，由于我们要将 $nums$ 拆分成 $n / 2$ 个数对，根据猜想，我们得到的数对序列为：
$$
(nums[0], nums[n - 1]), (nums[1], nums[n - 2]), ... , (nums[(n / 2) - 1], nums[n / 2])
$$

换句话说，构成答案的数对必然是较小数取自有序序列的左边，较大数取自有序序列的右边，且与数组中心对称。

假设最大数对是 $(nums[i], nums[j])$，其中 $i < j$，记两者之和为 $ans = nums[i] + nums[j]$。

反证法证明，不存在别的数对组合会比 $(nums[i], nums[j])$ 更优：

假设存在数对 $(nums[p], nums[q])$ 与 $(nums[i], nums[j])$ 进行调整使答案更优。

接下来分情况讨论：

• 调整为 $(nums[i], nums[p])$ 和 $(nums[q], nums[j])$：此时最大数对答案为 $nums[q] + nums[j]$，显然 $nums[q] + nums[j] >= nums[i] + nums[j] = ans$。我们要最小化最大数对和，因此该调整方案不会让答案更好；
• 调整为 $(nums[i], nums[q])$ 和 $(nums[p], nums[j])$：此时最大数对答案为 $\max(nums[i] + nums[q], nums[p] + nums[j]) = nums[p] + nums[j] >= nums[i] + nums[j] = ans$。我们要最小化最大数对和，因此该调整方案不会让答案更好；

上述分析可以归纳推理到每一个“非对称”的数对配对中。

至此我们得证，将原本对称的数对调整为不对称的数对，不会使得答案更优，即贪心解可取得最优解。

---

贪心

对原数组 $nums$ 进行排序，然后从一头一尾开始往中间组「数对」，取所有数对中的最大值即是答案。

代码：

###Java

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = nums[0] + nums[n - 1];
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            ans = Math.max(ans, nums[i] + nums[j]);
        }
        return ans;
    }
}

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(\log{n})$

---

答疑

关于「证明」部分，不少小伙伴有一些疑问，觉得挺有代表性的，特意加到题解内。

Q1. 「证明」部分是不是缺少了“非对称”得最优的情况？

A1. 并没有，证明的基本思路如下：

1. 猜想对称组数对的方式，会得到最优解；

2. 证明非对称数组不会被对称数对方式更优。

然后我们证明了“非对称方式”不会比“对称方式”更优，因此“对称方式”可以取得最优解。

至于非对称和非对称之间怎么调整，会更优还是更差，我不关心，也不需要证明，因为已经证明了非对称不会比对称更优。

Q2. 证明部分的图 $p$、$q$ 是在 $i$、$j$ 内部，那么其他 $p$、$q$、$i$、$j$ 大小关系的情况呢？

A2. 有这个疑问，说明没有重点理解「证明」中的加粗部分（原话）：

上述分析可以归纳推理到每一个“非对称”的数对配对中。

也就是说，上述的分析是可以推广到每一步都成立的，包括第一步，当 $i$ 为排序数组的第一位原始，$j$ 为排序数组中最后一位时，任意 $p$ 和 $q$ 都是在 $i$、$j$ 内部的。

因此，「证明」对边界情况成立，同时对任意不成“对称”关系的数对也成立（其实也就是「证明」部分中的原话）。

更大白话一点是：对于任意“非对称”的数对组合，将其调整为“对称”数对组合，结果不会变差。

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

方法一：排序 + 贪心

提示 $1$

数组内只有两个数的情况是平凡的。我们可以考虑数组中只有四个数 $x_1 \le x_2 \le x_3 \le x_4$ 的情况。此时 $(x_1, x_4), (x_2, x_3)$ 的拆分方法对应的最大数对和一定是最小的。

提示 $1$ 解释

我们可以枚举所有的拆分方法。除了上文的拆分方法外还有两种拆分方法：

• $(x_1, x_3), (x_2, x_4)$

  此时 $x_2 + x_4 \ge x_1 + x_4$ 且 $x_2 + x_4 \ge x_2 + x_3$。

  那么 $\max(x_1+x_3,x_2+x_4) \ge x_2 + x_4 \ge \max(x_1+x_4,x_2+x_3)$。

• $(x_1, x_2), (x_3, x_4)$

  同样地，$\max(x_1+x_2,x_3+x_4) \ge x_3 + x_4 \ge \max(x_1+x_4,x_2+x_3)$。

提示 $2$

对于 $n$ 个数（$n$ 为偶数）的情况，上述的条件对应的拆分方法，即第 $k$ 大与第 $k$ 小组成的 $n / 2$ 个数对，同样可以使得最大数对和最小。

提示 $2$ 解释

我们可以类似 提示 $1$ 对所有数建立全序关系，即 $x_1 \le \cdots \le x_n$。我们需要证明，任意的拆分方法得到的最大数对和一定大于等于给定的拆分方法得到的最大数对和。

我们可以考虑上述命题的充分条件：假设给定拆分方法中的数对和 $x_k + x_{n+1-k}$ 在 $k = k'$ 时最大，那么对于任意的拆分方法，都存在一组 $u, v$ 使得 $x_u + x_v \ge x_{k'} + x_{n+1-k'}$。

我们可以用反证法证明。

同样，我们假设 $u < v$，那么使得 $x_v \ge x_{n+1-k'}$ 的 $v$ 的取值一共有 $k'$ 种。即闭区间 $[n+1-k',n]$ 中的所有整数。对于这些 $v$ 组成的数对，如果想使得 $x_u + x_v < x_{k'} + x_{n+1-k'}$ 恒成立，必须要 $x_u < x_{k'}$。此时需要有 $k'$ 个不同的 $u$ 的取值，但只有闭区间 $[1,k'-1]$ 中的 $k'-1$ 个整数满足 $x_u < x_{k'}$ 的条件，这就产生了矛盾。

因此，一定存在一组 $u, v$ 使得 $x_u + x_v \ge x_{k'} + x_{n+1-k'}$。

思路与算法

根据 提示 $2$，我们需要将 $\textit{nums}$ 排序。排序后，我们遍历每一个第 $k$ 大与第 $k$ 小组成的数对，计算它们的和，并维护这些和的最大值。同样根据 提示 $2$，遍历完成后求得的最大数对和就是满足要求的最小值。

代码

###C++

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n / 2; ++i) {
            res = max(res, nums[i] + nums[n - 1 - i]);
        }
        return res;
    }
};

###Java

class Solution {
    public int minPairSum(int[] nums) {
        int n = nums.length;
        int res = 0;
        Arrays.sort(nums);
        for (int i = 0; i < n / 2; ++i) {
            res = Math.max(res, nums[i] + nums[n - 1 - i]);
        }
        return res;
    }
}

###C#

public class Solution {
    public int MinPairSum(int[] nums) {
        int n = nums.Length;
        int res = 0;
        Array.Sort(nums);
        for (int i = 0; i < n / 2; ++i) {
            res = Math.Max(res, nums[i] + nums[n - 1 - i]);
        }
        return res;
    }
}

###Python

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        nums.sort()
        for i in range(n // 2):
            res = max(res, nums[i] + nums[n-1-i])
        return res

###JavaScript

var minPairSum = function(nums) {
    const n = nums.length;
    let res = 0;
    nums.sort((a, b) => a - b);
    for (let i = 0; i < Math.floor(n / 2); i++) {
        res = Math.max(res, nums[i] + nums[n - 1 - i]);
    }
    return res;
};

###go

func minPairSum(nums []int) (ans int) {
    sort.Ints(nums)
    n := len(nums)
    for i, val := range nums[:n/2] {
        ans = max(ans, val+nums[n-1-i])
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

###C

int cmp(int *a, int *b) {
    return *a - *b;
}

int minPairSum(int *nums, int numsSize) {
    int res = 0;
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize / 2; ++i) {
        res = fmax(res, nums[i] + nums[numsSize - 1 - i]);
    }
    return res;
}

复杂度分析

• 时间复杂度：$O(n\log n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。排序 $\textit{nums}$ 的时间复杂度为 $O(n\log n)$，遍历维护最大数对和的时间复杂度为 $O(n)$。

• 空间复杂度：$O(\log n)$，即为排序的栈空间开销。

你可能猜了一个结论：把最小的数和最大的数配对，把第二小的数和第二大的数配对，依此类推。注意题目保证 $n$ 是偶数。

但是，如何证明这样做是对的？

设 $\textit{nums}$ 排序后的结果为 $a_1\le a_2\le \cdots \le a_n$。

首先证明，$a_1$ 与 $a_n$ 配对是最优的。

设 $a_i$ 和 $a_j$ 是数组中的另外两个数，考虑如下两种配对方案：

• $(a_1,a_i)$ 和 $(a_j,a_n)$。最大数对和为 $M_1 = \max(a_1+a_i,a_j+a_n,其他数对和)$。
• $(a_1,a_n)$ 和 $(a_i,a_j)$。最大数对和为 $M_2 = \max(a_1+a_n,a_i+a_j,其他数对和)$。

由于 $a_1\le a_j$，$a_i\le a_n$，所以 $a_1+a_i\le a_j+a_n$，所以 $M_1 = \max(a_j+a_n,其他数对和)$。

由于 $a_1+a_n\le a_j+a_n$ 且 $a_i+a_j\le a_j+a_n$，所以 $\max(a_1+a_n,a_i+a_j)\le a_j+a_n$，所以 $M_2\le M_1$。

这意味着，对于任意最优配对方案，将其调整为 $a_1$ 和 $a_n$ 配对，不会让最大数对和变得更大。所以存在最优配对方案，其中 $a_1$ 和 $a_n$ 是配对的。

去掉 $a_1$ 和 $a_n$（已配对），问题变成一个规模更小的子问题（$n-2$ 个数），同理可得其他数的配对方式。

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return max(nums[i] + nums[-1 - i] for i in range(n // 2))

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n / 2; i++) {
            ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
}

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n / 2; i++) {
            ans = max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int minPairSum(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans = 0;
    for (int i = 0; i < numsSize / 2; i++) {
        ans = MAX(ans, nums[i] + nums[numsSize - 1 - i]);
    }
    return ans;
}

func minPairSum(nums []int) (ans int) {
slices.Sort(nums)
n := len(nums)
for i, x := range nums[:n/2] {
ans = max(ans, x+nums[n-1-i])
}
return
}

var minPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n / 2; i++) {
        ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
    }
    return ans;
};

impl Solution {
    pub fn min_pair_sum(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable();
        let n = nums.len();
        let mut ans = 0;
        for i in 0..n / 2 {
            ans = ans.max(nums[i] + nums[n - 1 - i]);
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。瓶颈在排序上。
• 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

专题训练

见下面贪心题单的「§1.2 单序列配对」和「§1.7 交换论证法」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府