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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:07:56 2023-09-13 11:07:56 Updated    

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

这里整理一下 [ 在数组中选取子集，达到某一目标 ] 这类问题的通用解法。

  • 类型1 : 目标值明确，可以把目标值看出背包容量，数组值看做物品，转成背包问题
  • 类型2 : 目标值不明确，容量不知道，不能用背包，只能枚举子集的和

本题
1755.最接近目标值的子序列和
题意:目标值t, 子序列和sum, 求min = abs(sum - target)的最小值。
目标值不明确，背包容量不确定，不能转为背包问题，只能二分拆数组，来降低复杂度，然后枚举子数组的子集的和，最后用双指针指向两个子集和的元素，不断逼近目标值。
有人看到这里可能觉得是不是写错了，这题题目已经给出了目标值，为什么还说是目标值不明确的呢？
原因在于，题目给的target不是我们最后要组合的目标值，题目要我们求的是min的最小值，这里的最小值我们在解题之前是不知道的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        int n = nums.size();
        int half = n / 2;
        int ls = half, rs = n - half;
        
        vector<int> lsum(1 << ls, 0);
        for (int i = 1; i < (1 << ls); i++) {
            for (int j = 0; j < ls; j++) {
                if ((i & (1 << j)) == 0) continue;
                lsum[i] = lsum[i-(1<<j)] + nums[j];
                break;
            }
        }
        vector<int> rsum(1 << rs, 0);
        for (int i = 1; i < (1 << rs); i++) {
            for (int j = 0; j < rs; j++) {
                if ((i & (1 << j)) == 0) continue;
                rsum[i] = rsum[i-(1<<j)] + nums[ls+j];
                break;
            }
        }
        sort(lsum.begin(), lsum.end());
        sort(rsum.begin(), rsum.end());
        
        int ret = INT_MAX;
        for (int x: lsum) {
            ret = min(ret, abs(goal - x));
        }
        for (int x: rsum) {
            ret = min(ret, abs(goal - x));
        }
        
        int i = 0, j = rsum.size() - 1;
        while (i < lsum.size() && j >= 0) {
            int s = lsum[i] + rsum[j];
            ret = min(ret, abs(goal - s));
            if (s > goal) {
                j--;
            } else {
                i++;
            }
        }
        return ret;
    }
};

2035.将数组分成两个数组并最小化数组和的差
和1755思路一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size();
        int totalSum = 0;
        for (auto item : nums) {
            totalSum += item;
        }
        int half = n >> 1;
        vector<int> nums1(nums.begin(), nums.begin() + half);
        vector<int> nums2(nums.begin() + half, nums.end());
        int totalState = 1 << half;
        vector<int> sumA(totalState, 0);
        vector<int> sumB(totalState, 0);
        map<int, vector<int>> sumMap1, sumMap2;
        sumMap1[0].push_back(0);
        sumMap2[0].push_back(0);
        for (int s = 1; s < totalState; ++s) {
            int lowBit = s & (-s);
            int low = ffs(s) - 1;
            int left = s - lowBit;
            sumA[s] = sumA[left] + nums1[low];
            int bitNum = bitset<32>(s).count();
            sumMap1[bitNum].push_back(sumA[s]);
        }
        for (int s = 1; s < totalState; ++s) {
            int lowBit = s & (-s);
            int low = ffs(s) - 1;
            int left = s - lowBit;
            sumB[s] = sumB[left] + nums2[low];
            int bitNum = bitset<32>(s).count();
            sumMap2[bitNum].push_back(sumB[s]);
        }
        for (auto& pair : sumMap2) {
            auto& vec = pair.second;
            std::sort(vec.begin(), vec.end());
        }
        int ans = INT_MAX;
        for (int i = 0; i <= half; ++i) {
            auto& vec1 = sumMap1[i];
            auto& vec2 = sumMap2[half - i];
            for (auto x : vec1) {
                int id = lower_bound(vec2.begin(), vec2.end(), totalSum / 2 - x) - vec2.begin();
                int y = -1;
                if (id < vec2.size()) {
                    y = vec2[id];
                    ans = std::min(ans, abs(totalSum - (x + y) - (x + y)));
                }
                if (id > 0) {
                    y = vec2[id - 1];
                    ans = std::min(ans, abs(totalSum - (x + y) - (x + y)));
                }
            }
        }
        return ans;
    }
};

805.数组的均值分割
同1755

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<double> make(vector<double> nums){ // 枚举子序列的和
        int n = nums.size();
        int totalState = 1 << n;
        vector<double> sum(totalState, 0);
        for (int i = 1; i < totalState; ++i) {
            int lowBit = i & (-i);
            int bit = ffs(i);
            int left = i - lowBit;
            sum[i] = sum[left] + nums[bit - 1];
        }
        return sum;
    }
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        if(n == 1) return false;
        for(int& ev: nums) sum += ev;
        vector<double> dnums(n);
        for(int i = 0; i < n; ++i){
            dnums[i] = nums[i] - (double)sum / n;
        }
        // 获取所有子序列的和
        vector<double> left = make({dnums.begin(), dnums.begin() + n / 2});
        vector<double> right = make({dnums.begin() + n / 2, dnums.end()});
        // 先判断是否能独自构成答案，注意不能从0开始枚举，0表示不贡献任何元素
        for(int i = 1; i < left.size(); ++i){
            if(fabs(left[i]) < 1e-5) return true;
        }
        left.erase(left.begin()); left.pop_back(); // 删除全贡献和全不贡献的情况
        for(int i = 1; i < right.size(); ++i){
            if(fabs(right[i]) < 1e-5) return true;
        }
        right.erase(right.begin()); right.pop_back();
        sort(left.rbegin(), left.rend());
        sort(right.begin(), right.end());
        int l = 0, r = 0; // 双指针
        while(l < left.size() && r < right.size()){
            double ev = left[l] + right[r];
            if(fabs(ev) < 1e-5) return true;
            else if(ev > 0) l++;
            else r++;
        }
        return false;
    }
};

416.分割等和子集
题意:把数组分为两个部分，使每个部分的和相同。
目标值明确，目标值 = sum / 2，可以把sum / 2看做背包容量，转化为背包容量为sum / 2，数组中的元素是否能恰好装满背包的问题，也就是常说的01背包问题。
注：为什么要强调是否恰好呢？
因为和恰好装满和不恰好装满，数组的初始化是有区别的。
恰好装满的初始化:dp[0] = 0 | true，dp[1.....Tar] = 无效值 | false(正无穷或负无穷);
不要求完全装满dp[0......Tar] = 0 | true;
背包九讲大概是这么讲的：如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing “恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是false、+∞、-∞(无效值)。如果背包并非必须被装满，那么任何容量的背包都有一个合法解”什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false;

        int target = sum >> 1;
        vector<bool> dp(target, false);
        dp[0] = true;

        for(int i = 0; i < n; ++i) {
            for(int j = target; j >= 0; --j) {
                if (j >= nums[i]) {
                    dp[j] = dp[j] | dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
};

494.目标和
题意:给数组里的每个数字，添加正负号得到目标值target。
目标值明确，题目给出target，数组和sum，正数和sumA，负数和sumB，有以下关系:

1
2
3
sumA + sumB = sum
sumA - sumB = target
推导出 : sumA = (sum + target) / 2

转化为 : 在数组中选取出部分元素，给它们加上+号，这些元素和，也就是背包容量为sumA的方案数，同样是01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int T) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (T > sum || T < -sum || T + sum < 0 || (T + sum) % 2 == 1) {
            return 0;
        }
        int target = (T + sum) / 2;
        int n = nums.size();

        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = target; j >= 0; --j) {
                if (j >= nums[i]) {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
};

看到这里如果有收获，能点一个赞，就是对我最大的鼓励了^_^

 Comments
On this page
1755-最接近目标值的子序列和