题目描述

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

给你一个整数数组 nums 和一个目标值 goal 。

你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。

返回 abs(sum - goal) 可能的 最小值 。

注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。

示例

输入：nums = [5,-7,3,5], goal = 6
输出：0
解释：选择整个数组作为选出的子序列，元素和为 6 。子序列和与目标值相等，所以绝对差为 0 。

数据范围

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

思路

由于nums的长度为不超过40，因此首先想到能否基于状态压缩法来遍历所有的子序列，逐一进行计算。在一个数组中选出一个子序列，每个元素只有“选”或者“不选”两种状态，所有元素都被给予一个状态即可得到一个子序列。长度为40的数组即可将所有元素的状态信息压缩进一个64位的整数中。然而，子序列最多有2^40种情况，为10^12量级，显然会超时。

于是我们考虑是否能降低计算复杂度。由于超时是数组的长度导致的，所以考虑能否在更小的规模上运用上述思路。我们发现，如果将数组分为左右两部分来考虑，那么原数组上的一个子序列就成为两个子数组上的子序列。显然，原数组上的一个状态与子数组上的一对状态是一一对应的。因此，我们可以放心地遍历子数组上的全部状态，而不会漏掉原数组上的任何一个状态或者引入其它不存在的状态。

上述方式在计算状态时减小了问题的规模，显然我们不能再根据子数组上的状态一个一个把完整的状态拼凑出来，否则前面的问题分解就没有意义了。我们的目标是从两个数组中各选出一个状态，使得完整的子序列的元素和与目标的“距离”最小。我们使用基于两个排序数组的双指针法。设两个升序排列的数组为a、b。令p指向a的第一个元素，q指向b的最后一个元素。在每一次迭代中，如果两个元素之和大于目标值，就左移q；否则右移p。稍后给出这一方法的正确性证明。

代码

int minAbsDifference(vector<int>& nums, int goal) {
    int n = nums.size();

    int lsz = n / 2, rsz = n - lsz;
    vector<int> left_sum(1 << lsz, 0), right_sum(1 << rsz, 0);
    for (int state = 0; state < (1 << lsz); ++state) {
        for (int i = 0; i < lsz; ++i) {
            if (state & (1 << i)) {
                left_sum[state] += nums[i];
            }
        }
    }
    for (int state = 0; state < (1 << rsz); ++state) {
        for (int i = 0; i < rsz; ++i) {
            if (state & (1 << i)) {
                right_sum[state] += nums[lsz + i];
            }
        }
    }

    sort(left_sum.begin(), left_sum.end());
    sort(right_sum.begin(), right_sum.end());
    
    int res = INT_MAX;
    int p = 0, q = right_sum.size() - 1;
    while (p < left_sum.size() && q >= 0) {
        int tmp = left_sum[p] + right_sum[q];
        res = min(res, abs(tmp - goal));
        tmp >= goal ? --q : ++p;
    }

    return res;
}

双指针法的正确性证明

记数组\(a\)的元素为\(a_1, a_2, ..., a_s\)，数组\(b\)的元素为\(b_1,b_2,...,b_t\)。

反证法：若迭代过程中没有计算过最优的元素对，且最优的元素对为\(a_i,b_j\)，不妨设\(a_i,b_j\geq goal\)。考虑\(p\)指向\(a_i\)时\(q\)的位置。显然，\(q\)一定位于\(b_j\)左边的位置。否则，根据迭代算法，在\(p\)保持不动的情况下\(q\)一定会从\(b_j\)右侧走到\(b_j\)。设某一次迭代时\(q\)指向\(b_{j'}\)，显然，\(a_i+b_{j'}<goal\)，否则\(a_i,b_j\)将不是最优解。考虑迭代过程，要达到此状态，要么是\(p\)右移一位，要么是\(q\)左移一位。如果是\(q\)左移一位，则有\(a_i+b_{j'+1}>=goal\)，但\(j'+1<j\)，与\(a_i,b_j\)是最优解矛盾。因此，是由\(p\)右移一位转移到此状态的。于是考虑上一个状态：\(p\)指向\(i-1\)，\(q\)指向\(j'\)。显然\(a_{i-1}+b_{j'}<goal\)，类似地，可以推知这个状态也是由\(p\)右移而来的。按同样的方法往前推，直到\(p\)指向1，\(q\)指向\(j'\)，但这一状态无法再由\(p\)右移一位或者是\(q\)左移一位得到，矛盾。

举一反三

• 2035. 将数组分成两个数组并最小化数组和的差 （难度更大一些）