1755. 最接近目标值的子序列和

https://leetcode-cn.com/problems/closest-subsequence-sum/

• 1755. 最接近目标值的子序列和

  • 题目描述

  • 方法1：暴力法

    • 思路

    • 复杂度分析

    • 代码

  • 方法2：双向搜索

    • 思路

    • 复杂度分析

    • 代码

题目描述

给你一个整数数组 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];
  }
};

更多题解可以访问：https://github.com/suukii/91-days-algorithm