1755. 最接近目标值的子序列和
https://leetcode-cn.com/problems/closest-subsequence-sum/
题目描述
给你一个整数数组 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/closest-subsequence-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。方法1：暴力法
思路
首先尝试用最简单直接的思路来解题：
枚举
nums的所有子集，找到子集和最接近goal的那个
如果不知道怎么枚举子集可以先做下这道题 78.子集。
复杂度分析
时间复杂度：$O(2^N)$，N 为 nums 的长度。
空间复杂度：$O(N)$，N 为 nums 的长度，递归栈的深度。
代码
JavaScript Code
/**
* @param {number[]} nums
* @param {number} goal
* @return {number}
*/
var minAbsDifference = function(nums, goal) {
return dfs(nums, 0, 0);
function dfs(nums, pos, sum) {
// 对 nums 的所有元素作出选择后确定了子集
// 返回子集和与 goal 的差值
if (pos == nums.length) return Math.abs(sum - goal);
// prune
// 0 是可能的最小差值了，没必要继续搜索
if (sum === goal) return 0;
// 选当前数字
const a = dfs(nums, pos + 1, sum + nums[pos]);
// 不选当前数字
const b = dfs(nums, pos + 1, sum);
// 目标是找到最小的差值
return Math.min(a, b);
}
};方法2：双向搜索
思路
复杂度分析
时间复杂度：$O(2^m + mlogm)$，m 为 nums 长度的一半，$2^m$ 是枚举半截数组所有子集的时间，$mlogm$ 是。
空间复杂度：$O(1)$。
代码
JavaScript Code
/**
* @param {number[]} nums
* @param {number} goal
* @return {number}
*/
var minAbsDifference = function (nums, goal) {
const mid = nums.length >> 1;
// divide |nums| into two halves
// calculate sums of all possible subsets repectively
const leftSums = [];
dfs(nums, 0, mid, 0, leftSums);
const rightSums = [];
dfs(nums, mid, nums.length, 0, rightSums);
// we need to choose one value from |leftSums| and |rightSums| respectively
// the |x| and |y| chosen should sum closest to |goal|
// first sort |leftSums| for using binary search to find target
leftSums.sort((a, b) => a - b);
// now iterate through |rightSums|
// for each sum |x| from |rightSums|, go find the value closest to |goal-x| in |leftSums|, let's call it |closest|
// idealy |closest| will be equal to |goal-x|, which makes the total subset sum equal to |goal|
// if not so lucky, we pick the closest |closest| over the iteration
let minDiff = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < rightSums.length; i++) {
const x = rightSums[i];
const target = goal - x;
const closest = findClosest(leftSums, target);
const diff = Math.abs(target - closest);
minDiff = Math.min(diff, minDiff)
}
return minDiff
// ******************************************
function dfs(nums, start, end, currentSum, bucket) {
if (start == end) {
bucket.push(currentSum);
return;
}
dfs(nums, start + 1, end, currentSum + nums[start], bucket);
dfs(nums, start + 1, end, currentSum, bucket);
}
function findClosest(list, target) {
let l = 0,
r = list.length - 1,
m = 0;
while (l <= r) {
m = ((r - l) >> 1) + l;
if (list[m] == target) return target
if (list[m] < target) l = m + 1
else r = m - 1
}
if (l >= list.length) return list[r];
if (r < 0) return list[l];
return Math.abs(list[l] - target) < Math.abs(list[r] - target) ? list[l] : list[r];
}
};Last updated
Was this helpful?