最接近目标值的子序列和

题目

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

---

给你一个整数数组 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
• -10^7 <= nums[i] <= 10^7
• -10^9 <= goal <= 10^9

题解

方法一：

思路

折半搜索，二分或双指针。

注意到数组大小最多为40

我们枚举左一半长度的数组的所有子序列的和（共2^{n/2}种）存到有序集合a中，然后枚举右一半长度的数组的每个子序列之和x，可以通过在a中二分查找距离goal-x最近的数y，然后维护最小值min(goal-x-y)。时间复杂度O(2^{n/2} * logn)

也可以求出两个子序列集合a，b。然后通过双指针找到离goal最近的两数之和。时间复杂度O(2^{n/2})

代码

class Solution {
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        vector<int> a, b;
        int ans = abs(goal);
        int n = nums.size();
        for (int i=0; i<(1<<n/2); i++) {
            int cnt = 0;
            for (int j=0; j<n/2; j++) {
                if (i>>j&1) cnt += nums[j];
            }
            a.push_back(cnt);
        }

        // for (int i:st) cout << i << " "; cout << endl;
        for (int i=0; i<(1<<(n+1)/2); i++) {
            int cnt = 0;
            for (int j=0; j<(n+1)/2; j++) {
                if (i>>j&1) cnt += nums[j+n/2];
            }
            b.push_back(cnt);
        }
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        sort(b.begin(), b.end());
        b.erase(unique(b.begin(), b.end()), b.end());
        int l = 0, r = (int)b.size()-1;
        while (l<a.size() && r>=0) {
            ans = min(ans, abs(a[l]+b[r]-goal));
            if (a[l]+b[r]>goal) {
                r--;
            } else {
                l++;
            }
        }
        return ans;
    }
};