给你个整数数组 arr，其中每个元素都 不相同。
请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
每对元素对 [a,b] 如下：
登录a , b 均为数组 arr 中的元素a < bb - a 等于 arr 中任意两个元素的最小绝对差
示例 1：
输入：arr = [4,2,1,3] 输出：[[1,2],[2,3],[3,4]]
示例 2：
输入：arr = [1,3,6,10,15] 输出：[[1,3]]
示例 3：
输入：arr = [3,8,-10,23,19,-4,-14,27] 输出：[[-14,-10],[19,23],[23,27]]
提示：
2 <= arr.length <= 10^5-10^6 <= arr[i] <= 10^6数据范围为 $1e5$，我们不能通过枚举的方式遍历所有的点对找最小值。
我们可以对 arr 进行排序，容易得知差值最小值必然发生在排序数组的相邻元素之间，此时我们可以通过遍历排序数组并使用变量 min 记录当前差值最小值来统计答案。
代码：
###Java
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
List<List<Integer>> ans = new ArrayList<>();
int n = arr.length, min = arr[1] - arr[0];
for (int i = 0; i < n - 1; i++) {
int cur = arr[i + 1] - arr[i];
if (cur < min) {
ans.clear();
min = cur;
}
if (cur == min) {
List<Integer> temp = new ArrayList<>();
temp.add(arr[i]); temp.add(arr[i + 1]);
ans.add(temp);
}
}
return ans;
}
}
题太简单？今日份加餐：【面试高频题】难度 1.5/5，数据结构运用题 🎉 🎉
或是考虑加练如下「模拟」题 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 6. Z 字形变换 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 8. 字符串转换整数 (atoi) | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 12. 整数转罗马数字 | LeetCode 题解链接 | 中等 | 🤩🤩 |
| 59. 螺旋矩阵 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 65. 有效数字 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 73. 矩阵置零 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 89. 格雷编码 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 166. 分数到小数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 260. 只出现一次的数字 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 414. 第三大的数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 419. 甲板上的战舰 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 443. 压缩字符串 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 457. 环形数组是否存在循环 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 528. 按权重随机选择 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 539. 最小时间差 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 726. 原子的数量 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
排序后所有可能的最小绝对值由每对儿相邻的差构成
###Python3
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
m, ans = inf, []
for a, b in pairwise(sorted(arr)):
if (cur := b - a) < m:
m, ans = cur, [[a, b]]
elif cur == m:
ans.append([a, b])
return ans
###Java
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
List<List<Integer>> list = new ArrayList<>();
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length - 1; i++) {
int diff = arr[i + 1] - arr[i];
if (diff < min) {
min = diff;
list.clear();
List<Integer> cur = new ArrayList<>();
cur.add(arr[i]);
cur.add(arr[i + 1]);
list.add(cur);
} else if (diff == min) {
List<Integer> cur = new ArrayList<>();
cur.add(arr[i]);
cur.add(arr[i + 1]);
list.add(cur);
}
}
return list;
}
}
###TypeScript
function minimumAbsDifference(arr: number[]): number[][] {
arr.sort((a, b) => a - b)
let ans = new Array<Array<number>>(), min = Number.MAX_SAFE_INTEGER
for (let i = 0; i < arr.length - 1; i++) {
const cur = arr[i + 1] - arr[i]
if (cur < min) {
min = cur
ans = [[arr[i], arr[i + 1]]]
} else if (cur == min) {
ans.push([arr[i], arr[i + 1]])
}
}
return ans
};
###Go
func minimumAbsDifference(arr []int) (ans [][]int) {
sort.Ints(arr)
for i, min := 0, math.MaxInt32; i < len(arr) - 1; i++ {
if diff := arr[i + 1] - arr[i]; diff < min {
min = diff
ans = [][]int{[]int{arr[i], arr[i + 1]}}
} else if diff == min {
ans = append(ans, []int{arr[i], arr[i + 1]})
}
}
return
}
思路与算法
首先我们对数组 $\textit{arr}$ 进行升序排序。这样一来，拥有「最小绝对差」的元素对只能由有序数组中相邻的两个元素构成。
随后我们对数组 $\textit{arr}$ 进行一次遍历。当遍历到 $\textit{arr}[i]$ 和 $\textit{arr}[i+1]$ 时，它们的差为 $\delta = \textit{arr}[i+1] - \textit{arr}[i]$。我们使用一个变量 $\textit{best}$ 存储当前遇到的最小差，以及一个数组 $\textit{ans}$ 存储答案：
如果 $\delta < \textit{best}$，那么说明我们遇到了更小的差值，需要更新 $\textit{best}$，同时 $\textit{ans}$ 清空并放入 $\textit{arr}[i]$ 和 $\textit{arr}[i+1]$；
如果 $\delta = \textit{best}$，那么我们只需要将 $\textit{arr}[i]$ 和 $\textit{arr}[i+1]$ 放入答案数组即可。
代码
###C++
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
int n = arr.size();
sort(arr.begin(), arr.end());
int best = INT_MAX;
vector<vector<int>> ans;
for (int i = 0; i < n - 1; ++i) {
if (int delta = arr[i + 1] - arr[i]; delta < best) {
best = delta;
ans = {{arr[i], arr[i + 1]}};
}
else if (delta == best) {
ans.emplace_back(initializer_list<int>{arr[i], arr[i + 1]});
}
}
return ans;
}
};
###Java
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
int n = arr.length;
Arrays.sort(arr);
int best = Integer.MAX_VALUE;
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for (int i = 0; i < n - 1; ++i) {
int delta = arr[i + 1] - arr[i];
if (delta < best) {
best = delta;
ans.clear();
List<Integer> pair = new ArrayList<Integer>();
pair.add(arr[i]);
pair.add(arr[i + 1]);
ans.add(pair);
} else if (delta == best) {
List<Integer> pair = new ArrayList<Integer>();
pair.add(arr[i]);
pair.add(arr[i + 1]);
ans.add(pair);
}
}
return ans;
}
}
###C#
public class Solution {
public IList<IList<int>> MinimumAbsDifference(int[] arr) {
int n = arr.Length;
Array.Sort(arr);
int best = int.MaxValue;
IList<IList<int>> ans = new List<IList<int>>();
for (int i = 0; i < n - 1; ++i) {
int delta = arr[i + 1] - arr[i];
if (delta < best) {
best = delta;
ans.Clear();
IList<int> pair = new List<int>();
pair.Add(arr[i]);
pair.Add(arr[i + 1]);
ans.Add(pair);
} else if (delta == best) {
IList<int> pair = new List<int>();
pair.Add(arr[i]);
pair.Add(arr[i + 1]);
ans.Add(pair);
}
}
return ans;
}
}
###Python
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
n = len(arr)
arr.sort()
best, ans = float('inf'), list()
for i in range(n - 1):
if (delta := arr[i + 1] - arr[i]) < best:
best = delta
ans = [[arr[i], arr[i + 1]]]
elif delta == best:
ans.append([arr[i], arr[i + 1]])
return ans
###C
static inline int cmp(const void *pa, const void *pb) {
return *(int *)pa - *(int *)pb;
}
int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes){
qsort(arr, arrSize, sizeof(int), cmp);
int best = INT_MAX;
int **ans = (int **)malloc(sizeof(int *) * (arrSize - 1));
int pos = 0;
for (int i = 0; i < arrSize - 1; ++i) {
int delta = arr[i + 1] - arr[i];
if (delta < best) {
best = delta;
for (int j = 0; j < pos; j++) {
free(ans[j]);
}
pos = 0;
ans[pos] = (int *)malloc(sizeof(int) * 2);
memcpy(ans[pos], arr + i, sizeof(int) * 2);
pos++;
}
else if (delta == best) {
ans[pos] = (int *)malloc(sizeof(int) * 2);
memcpy(ans[pos], arr + i, sizeof(int) * 2);
pos++;
}
}
*returnSize = pos;
*returnColumnSizes = (int *)malloc(sizeof(int) * pos);
for (int i = 0; i < pos; i++) {
(*returnColumnSizes)[i] = 2;
}
return ans;
}
###JavaScript
var minimumAbsDifference = function(arr) {
const n = arr.length;
arr.sort((a, b) => a - b);
let best = Number.MAX_VALUE;
let ans = [];
for (let i = 0; i < n - 1; ++i) {
let delta = arr[i + 1] - arr[i];
if (delta < best) {
best = delta;
ans = [];
const pair = [];
pair.push(arr[i]);
pair.push(arr[i + 1]);
ans.push(pair);
} else if (delta === best) {
const pair = [];
pair.push(arr[i]);
pair.push(arr[i + 1]);
ans.push(pair);
}
}
return ans;
};
###go
func minimumAbsDifference(arr []int) (ans [][]int) {
sort.Ints(arr)
for i, best := 0, math.MaxInt32; i < len(arr)-1; i++ {
if delta := arr[i+1] - arr[i]; delta < best {
best = delta
ans = [][]int{{arr[i], arr[i+1]}}
} else if delta == best {
ans = append(ans, []int{arr[i], arr[i+1]})
}
}
return
}
复杂度分析
时间复杂度：$O(n \log n)$，其中 $n$ 是数组 $\textit{arr}$ 的长度。排序需要的时间为 $O(n \log n)$，遍历需要的是时间为 $O(n)$，因此总时间复杂度为 $O(n \log n)$。
空间复杂度：$O(\log n)$，即为排序需要使用的栈空间。这里不计入返回值需要使用的空间。
为方便计算差值，先把 $\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
}
}
欢迎关注 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 <= 10000 <= 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;
}
}
题太简单？来看一道 更贴合笔试/面试的滑动窗口综合题 🎉 🎉
或是加练其他「滑动窗口」内容 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 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.length2 <= n <= 105n 是 偶数 。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$ 进行排序，然后从一头一尾开始往中间组「数对」，取所有数对中的最大值即是答案。
代码：
###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;
}
}
关于「证明」部分，不少小伙伴有一些疑问，觉得挺有代表性的，特意加到题解内。
Q1. 「证明」部分是不是缺少了“非对称”得最优的情况？
A1. 并没有，证明的基本思路如下：
猜想对称组数对的方式，会得到最优解；
证明非对称数组不会被对称数对方式更优。
然后我们证明了“非对称方式”不会比“对称方式”更优，因此“对称方式”可以取得最优解。
至于非对称和非对称之间怎么调整，会更优还是更差，我不关心，也不需要证明，因为已经证明了非对称不会比对称更优。
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\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
}
}
见下面贪心题单的「§1.2 单序列配对」和「§1.7 交换论证法」。
欢迎关注 B站@灵茶山艾府
