最接近目标值的子序列和

Trace

最接近目标值的子序列和

传送门：https://leetcode-cn.com/problems/closest-subsequence-sum/

Problem

给你一个整数数组 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：

1 2	输入：nums = [1,2,3], goal = -7 输出：7

提示：

1
2
3

1 <= nums.length <= 40
-10^7 <= nums[i] <= 10^7
-10^9 <= goal <= 10^9

思路

枚举子集的基础题目：https://leetcode-cn.com/problems/subsets/

两种求所有子集的方法：

$dfs$
位运算

枚举所有子集的时间复杂度为$2^n$，$n=40$，加上每次需要求和运算，时间复杂度太高。

一个技巧：将$n=40$的数组拆成两部分，每部分元素个数为20，枚举每一部分所有子集的时间复杂度为$2^{20}\approx10^6$，接着枚举每一部分所有子集的和，记为$sum1$，$sum2$，时间复杂度$O((n/2)*2^{n/2})$，大概在$10^7$左右。

原数组的子序列和，必然为下列三者之一：

$sum1$中某个元素
$sum2$中某个元素
$sum1$中某个元素与$sum2$中某个元素之和

前两种情况直接遍历就可以得到，第三种情况为给定两个有序数组，分别从两个数组中各取出一个数字，使他们的和最接近$goal$，相关题目：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/。

考虑双指针，将$i$指向$sum1$中第一个元素，将$j$指向$sum2$中最后一个元素，每次计算$sum1[i]$与$sum2[j]$的和$s$。

如果$s<goal$，则对于当前的$i$，剩余所有的$j$都不用考虑了（和只可能更小），于是将$i$右移一个位置；

如果$s>=goal$，则对于当前的$j$，剩余所有的$i$都不需要考虑了（和只可能更大），于是将$j$左移一个位置。

这部分排序时间复杂度为$O(2^{n/2}log{2^{n/2}})$，大概在$10^7$左右，双指针时间复杂度$O(2^{n/2})$。

程序

class Solution {
public:
    vector<int> sum1;
    vector<int> sum2;
    int minAbsDifference(vector<int>& nums, int goal) {
        int n=nums.size();
        // 位运算求subset
        for(int i=0;i<(1<<(n/2));i++){
            int sum=0;
            for(int j=0;j<n/2;j++){
                if(i&(1<<j)){
                    sum+=nums[j];
                }
            }
            sum1.push_back(sum);
        }
        for(int i=0;i<(1<<(n-n/2));i++){
            int sum=0;
            for(int j=0;j<(n-n/2);j++){
                if(i&(1<<j)){
                    sum+=nums[n/2+j];
                }
            }
            sum2.push_back(sum);
        }

        sort(sum1.begin(),sum1.end());
        sort(sum2.begin(),sum2.end());

        int Min=0x3f3f3f3f;
        for(int i=0;i<sum1.size();i++){
            if(abs(sum1[i]-goal)<Min){
                Min=abs(sum1[i]-goal);
            }
        }

        for(int i=0;i<sum2.size();i++){
            if(abs(sum2[i]-goal)<Min){
                Min=abs(sum2[i]-goal);
            }
        }

        // 从sum1中挑选一个数，从sum2中挑选一个数，使二者之和与goal的差最小
        // 双指针做法
        int i=0,j=sum2.size()-1;
        while(i<sum1.size()&&j>=0){
            Min=min(Min,abs(sum1[i]+sum2[j]-goal));
            if(sum1[i]+sum2[j]<=goal){
                i++;
            }
            else{
                j--;
            }
        }

        return Min;
    }
};