数组拆分

难度: Easy

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a₁, b₁), (a₂, b₂), ..., (a_n, b_n) ，使得从 1 到 n 的 min(a_i, b_i) 总和最大。

返回该 最大总和 。

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

提示：

1 <= n <= 10⁴
nums.length == 2 * n
-10⁴ <= nums[i] <= 10⁴

Submission

运行时间: 44 ms

内存: 17.9 MB

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        # nums.sort()
        # nums_len = len(nums)
        # i = 0
        # ans = 0
        # while i < nums_len - 1:
        #     ans += min(nums[i],nums[i + 1])
        #     i += 2
        # return ans

        nums.sort()
        return sum(nums[::2])

Explain

这道题的思路是先将数组按升序排序，然后把相邻的两个数分为一组，取每组的第一个数求和。因为分组后的第一个数一定小于等于第二个数，所以每组的 min 值就是第一个数。把所有分组的 min 值加起来就得到了最大总和。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()  # 对数组按升序排序
        return sum(nums[::2])  # 遍历下标为偶数的元素求和，即每个分组的第一个数

Explore

排序是为了确保能够有效地配对数字以最大化最小值的总和。通过排序，我们可以将较小的数字放在一起，较大的数字放在一起，这样在分组时可以避免较大数字被较小数字'拖累'，从而达到提高每对中最小值总和的目的。

在数组已经排序的情况下，相邻的两个数字构成一对可以确保在每对中形成的两个数字差距最小。这样做的结果是使得每组中较小的数字尽可能大，从而使得所有组中最小值的总和达到可能的最大值。

在排序数组中，当两个数字成对时，第一个数字（即较小的数字）自然是每对的最小值。由于题目要求的是最大化所有选定对的最小值之和，因此选取每对中的第一个数字（即每对的最小值）进行求和是符合题目要求的最佳选择。

是的，这种方法仍然适用。即使数组中有重复的数字，排序和分组的逻辑依然有效。重复的元素在排序后会彼此相邻，从而在分组时仍然会按照相邻分组的逻辑被处理。因此，这种策略在数组元素有重复的情况下仍然能够正确地计算出最大的最小值之和。