LeetCode 题解工作台
最接近目标值的子序列和
给你一个整数数组 nums 和一个目标值 goal 。 你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。 返回 abs(sum - goal) 可能的 最小值 。 注意，数组的子…
6
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
每个数选或不选两种可能，所以 个数就有 种组合，由于 最大为 ，枚举 种组合显然会超时。 我们可以把数组分成左右两部分，分别求出两部分所有子序列和，记为 和 。最后，只需找到最接近 的 $left[i] + right[j]$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 nums 和一个目标值 goal 。
你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。
返回 abs(sum - goal) 可能的 最小值 。
注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
示例 1：
输入：nums = [5,-7,3,5], goal = 6 输出：0 解释：选择整个数组作为选出的子序列，元素和为 6 。 子序列和与目标值相等，所以绝对差为 0 。
示例 2：
输入：nums = [7,-9,15,-2], goal = -5 输出：1 解释：选出子序列 [7,-9,-2] ，元素和为 -4 。 绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。
示例 3：
输入：nums = [1,2,3], goal = -7 输出：7
提示：
1 <= nums.length <= 40-107 <= nums[i] <= 107-109 <= goal <= 109
解题思路
方法一：DFS + 二分查找
每个数选或不选两种可能，所以 个数就有 种组合，由于 最大为 ，枚举 种组合显然会超时。
我们可以把数组分成左右两部分，分别求出两部分所有子序列和，记为 和 。最后，只需找到最接近 的 。
时间复杂度 。
相似题目：
class Solution:
def minAbsDifference(self, nums: List[int], goal: int) -> int:
n = len(nums)
left = set()
right = set()
self.getSubSeqSum(0, 0, nums[: n // 2], left)
self.getSubSeqSum(0, 0, nums[n // 2 :], right)
result = inf
right = sorted(right)
rl = len(right)
for l in left:
remaining = goal - l
idx = bisect_left(right, remaining)
if idx < rl:
result = min(result, abs(remaining - right[idx]))
if idx > 0:
result = min(result, abs(remaining - right[idx - 1]))
return result
def getSubSeqSum(self, i: int, curr: int, arr: List[int], result: Set[int]):
if i == len(arr):
result.add(curr)
return
self.getSubSeqSum(i + 1, curr, arr, result)
self.getSubSeqSum(i + 1, curr + arr[i], arr, result)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you understand subset sum state transitions and meet-in-the-middle optimization.
- question_mark
Tests your ability to reduce exponential time via splitting and sorting sums.
- question_mark
Looks for correct handling of negative numbers and empty subsequences.
常见陷阱
外企场景- error
Attempting a full 2^n enumeration without splitting causes timeouts for n > 20.
- error
Failing to sort one half's sums prevents efficient binary search and correct minimum difference calculation.
- error
Overlooking empty subsequences or negative numbers can result in incorrect absolute difference computation.
进阶变体
外企场景- arrow_right_alt
Find the closest subsequence sum constrained to at most k elements.
- arrow_right_alt
Compute closest subsequence sum where elements must be consecutive in nums.
- arrow_right_alt
Determine closest subsequence product instead of sum, emphasizing DP state tracking.