LeetCode 题解工作台
从子集的和还原数组
存在一个未知数组需要你进行还原，给你一个整数 n 表示该数组的长度。另给你一个数组 sums ，由未知数组中全部 2 n 个 子集的和 组成（子集中的元素没有特定的顺序）。 返回一个长度为 n 的数组 ans 表示还原得到的未知数组。如果存在 多种 答案，只需返回其中 任意一个 。 如果可以由数组 …
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·结合·divide·conquer
答案摘要
class Solution: def recoverArray(self, n: int, sums: List[int]) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·divide·conquer 题型思路
题目描述
存在一个未知数组需要你进行还原，给你一个整数 n 表示该数组的长度。另给你一个数组 sums ，由未知数组中全部 2n 个 子集的和 组成（子集中的元素没有特定的顺序）。
返回一个长度为 n 的数组 ans 表示还原得到的未知数组。如果存在 多种 答案，只需返回其中 任意一个 。
如果可以由数组 arr 删除部分元素（也可能不删除或全删除）得到数组 sub ，那么数组 sub 就是数组 arr 的一个 子集 。sub 的元素之和就是 arr 的一个 子集的和 。一个空数组的元素之和为 0 。
注意：生成的测试用例将保证至少存在一个正确答案。
示例 1：
输入：n = 3, sums = [-3,-2,-1,0,0,1,2,3] 输出：[1,2,-3] 解释：[1,2,-3] 能够满足给出的子集的和： - []：和是 0 - [1]：和是 1 - [2]：和是 2 - [1,2]：和是 3 - [-3]：和是 -3 - [1,-3]：和是 -2 - [2,-3]：和是 -1 - [1,2,-3]：和是 0 注意，[1,2,-3] 的任何排列和 [-1,-2,3] 的任何排列都会被视作正确答案。
示例 2：
输入：n = 2, sums = [0,0,0,0] 输出：[0,0] 解释：唯一的正确答案是 [0,0] 。
示例 3：
输入：n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8] 输出：[0,-1,4,5] 解释：[0,-1,4,5] 能够满足给出的子集的和。
提示：
1 <= n <= 15sums.length == 2n-104 <= sums[i] <= 104
解题思路
方法一
class Solution:
def recoverArray(self, n: int, sums: List[int]) -> List[int]:
m = -min(sums)
sl = SortedList(x + m for x in sums)
sl.remove(0)
ans = [sl[0]]
for i in range(1, n):
for j in range(1 << i):
if j >> (i - 1) & 1:
s = sum(ans[k] for k in range(i) if j >> k & 1)
sl.remove(s)
ans.append(sl[0])
for i in range(1 << n):
s = sum(ans[j] for j in range(n) if i >> j & 1)
if s == m:
for j in range(n):
if i >> j & 1:
ans[j] *= -1
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates an understanding of subset sum problems.
- question_mark
Candidate leverages sorting to help identify key elements.
- question_mark
Candidate successfully applies divide and conquer techniques to reduce the problem size.
常见陷阱
外企场景- error
Confusing the order of subset sums and the actual array elements.
- error
Failing to account for multiple possible solutions, leading to incorrect assumptions about uniqueness.
- error
Not applying divide and conquer efficiently, leading to unnecessary recomputation.
进阶变体
外企场景- arrow_right_alt
Working with larger arrays, where the number of subset sums increases exponentially.
- arrow_right_alt
Optimizing for time and space complexity, especially in recursive solutions.
- arrow_right_alt
Handling edge cases where all array elements are zero, or negative values are involved.