LeetCode 题解工作台
将数组分成两个数组并最小化数组和的差
给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。 nums 中每个元素都需要放入两个数组之一。 请你返回 最小 的数组和之差。 示例 1： 输入： nums = [3,9,7,3] 输出： 2 …
7
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def minimumDifference(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。
请你返回 最小 的数组和之差。
示例 1：
输入：nums = [3,9,7,3] 输出：2 解释：最优分组方案是分成 [3,9] 和 [7,3] 。 数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。
示例 2：
输入：nums = [-36,36] 输出：72 解释：最优分组方案是分成 [-36] 和 [36] 。 数组和之差的绝对值为 abs((-36) - (36)) = 72 。
示例 3：
输入：nums = [2,-1,0,4,-2,-9] 输出：0 解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。 数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。
提示：
1 <= n <= 15nums.length == 2 * n-107 <= nums[i] <= 107
解题思路
方法一
class Solution:
def minimumDifference(self, nums: List[int]) -> int:
n = len(nums) >> 1
f = defaultdict(set)
g = defaultdict(set)
for i in range(1 << n):
s = cnt = 0
s1 = cnt1 = 0
for j in range(n):
if (i & (1 << j)) != 0:
s += nums[j]
cnt += 1
s1 += nums[n + j]
cnt1 += 1
else:
s -= nums[j]
s1 -= nums[n + j]
f[cnt].add(s)
g[cnt1].add(s1)
ans = inf
for i in range(n + 1):
fi, gi = sorted(list(f[i])), sorted(list(g[n - i]))
# min(abs(f[i] + g[n - i]))
for a in fi:
left, right = 0, len(gi) - 1
b = -a
while left < right:
mid = (left + right) >> 1
if gi[mid] >= b:
right = mid
else:
left = mid + 1
ans = min(ans, abs(a + gi[left]))
if left > 0:
ans = min(ans, abs(a + gi[left - 1]))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on generating all subset sums, which is O(2^n) per half, and combining with binary search gives O(2^n log(2^n)). Space complexity is O(2^n) for storing sums of each half. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for efficient handling of subset sums beyond brute-force partitioning.
- question_mark
Expect discussion of state transition dynamic programming and sum targeting.
- question_mark
Watch for correct edge case handling with negative integers.
常见陷阱
外企场景- error
Assuming a simple greedy split works; it fails with negative numbers.
- error
Not properly generating all subset sums with bitmasking, missing optimal partitions.
- error
Mishandling binary search rounding or bounds when combining halves.
进阶变体
外企场景- arrow_right_alt
Partition into k arrays instead of 2 while minimizing max-min sum difference.
- arrow_right_alt
Limit subset sums to positive integers only to simplify DP states.
- arrow_right_alt
Allow array length n up to 20, requiring pruning or meet-in-the-middle optimizations.