What is the best strategy to solve Array Partition efficiently?

Sort the array and sum every other element starting from the first. This guarantees maximum sum of minimums due to the greedy invariant.

Can negative numbers affect the greedy pairing approach?

No, the greedy invariant still holds for negative numbers; pairing consecutive sorted elements ensures the sum of minimums is maximized.

Is brute force ever feasible for Array Partition?

No, trying all pair combinations has exponential complexity and becomes impractical even for small n.

How does counting sort optimize this problem?

For arrays with elements in a limited range, counting sort sorts in O(n) time, preserving the greedy consecutive pairing strategy.

Why do we sum the first element of each sorted pair?

Summing the first element captures the minimum of each pair while respecting the greedy invariant that maximizes the total sum.

#561

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

数组拆分

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a 1 , b 1 ), (a 2 , b 2 ), ..., (a n , b n ) ，使得从 1 到 n 的 min(a i , b i ) 总和最大。返回该最大总和。示例 1：输入： nums = …

数组贪心排序计数排序

题目描述

给定长度为 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⁴

lightbulb

解题思路

方法一：排序

对于一个数对 $(a, b)$ ，我们不妨设 $a \leq b$ ，那么 $\min(a, b) = a$ 。为了使得总和尽可能大，我们取的 $b$ 应该与 $a$ 尽可能接近，这样可以保留更大的数。

因此，我们可以对数组 $nums$ 进行排序，然后将相邻的两个数分为一组，取每组的第一个数相加即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about greedy strategy versus brute force to test understanding of invariant validation.
question_mark
Expect reasoning on why pairing sorted consecutive elements maximizes the sum of minimums.
question_mark
Look for discussion of time-space trade-offs, such as using counting sort for bounded integer arrays.

warning

常见陷阱

外企场景

error
Attempting all possible pair combinations leads to exponential time complexity.
error
Pairing without sorting may violate the greedy invariant and produce suboptimal sums.
error
Misunderstanding that the sum of maximums in each pair is not the goal; the minimums drive the result.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the maximum sum if elements can be negative and positive, emphasizing the same greedy principle.
arrow_right_alt
Adapt the problem to k-sized groups instead of pairs, testing generalization of invariant reasoning.
arrow_right_alt
Determine the minimum sum of maximums of pairs, which flips the greedy selection logic.

help

常见问题

外企场景

继续练习

#581 最短无序连续子数组 #611 有效三角形的个数 #502 IPO