Hard

题目描述

给你一个整数数组 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^40 种可能，时间复杂度太高。

**中途相遇法（Meet in the Middle）**是解决此问题的最佳策略：

  1. 分割数组：将数组分成两部分，长度大致相等，每部分最多 20 个元素
  2. 生成子集和：对每一部分分别生成所有可能的子集和，复杂度降为 2^20
  3. 排序优化：将第一部分的所有子集和排序，便于后续二分查找
  4. 双指针搜索：遍历第二部分的每个子集和，用二分查找在第一部分中找到最接近 goal - sum2 的值

具体步骤：

  • 对于第二部分的每个子集和 sum2，我们需要在第一部分找到最接近 goal - sum2 的值
  • 使用二分查找找到不超过 goal - sum2 的最大值和不小于 goal - sum2 的最小值
  • 计算这两种组合与 goal 的差的绝对值，取最小值

这种方法将时间复杂度从 O(2^n) 优化到 O(2^(n/2) * log(2^(n/2)))，在 n=40 时有显著改善。

代码实现

class Solution {
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        int n = nums.size();
        int mid = n / 2;
        
        // 生成前半部分所有可能的子集和
        vector<int> leftSums;
        for (int mask = 0; mask < (1 << mid); mask++) {
            int sum = 0;
            for (int i = 0; i < mid; i++) {
                if (mask & (1 << i)) {
                    sum += nums[i];
                }
            }
            leftSums.push_back(sum);
        }
        
        sort(leftSums.begin(), leftSums.end());
        
        int result = abs(goal);
        
        // 生成后半部分所有可能的子集和，并与前半部分组合
        for (int mask = 0; mask < (1 << (n - mid)); mask++) {
            int sum = 0;
            for (int i = 0; i < n - mid; i++) {
                if (mask & (1 << i)) {
                    sum += nums[mid + i];
                }
            }
            
            int target = goal - sum;
            
            // 二分查找最接近target的值
            auto it = lower_bound(leftSums.begin(), leftSums.end(), target);
            
            if (it != leftSums.end()) {
                result = min(result, abs(sum + *it - goal));
            }
            if (it != leftSums.begin()) {
                --it;
                result = min(result, abs(sum + *it - goal));
            }
        }
        
        return result;
    }
};

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        mid = n // 2
        
        # 生成前半部分所有可能的子集和
        left_sums = []
        for mask in range(1 << mid):
            sum_val = 0
            for i in range(mid):
                if mask & (1 << i):
                    sum_val += nums[i]
            left_sums.append(sum_val)
        
        left_sums.sort()
        
        result = abs(goal)
        
        # 生成后半部分所有可能的子集和，并与前半部分组合
        for mask in range(1 << (n - mid)):
            sum_val = 0
            for i in range(n - mid):
                if mask & (1 << i):
                    sum_val += nums[mid + i]
            
            target = goal - sum_val
            
            # 二分查找最接近target的值
            import bisect
            pos = bisect.bisect_left(left_sums, target)
            
            if pos < len(left_sums):
                result = min(result, abs(sum_val + left_sums[pos] - goal))
            if pos > 0:
                result = min(result, abs(sum_val + left_sums[pos - 1] - goal))
        
        return result

public class Solution {
    public int MinAbsDifference(int[] nums, int goal) {
        int n = nums.Length;
        int mid = n / 2;
        
        // 生成前半部分所有可能的子集和
        List<int> leftSums = new List<int>();
        for (int mask = 0; mask < (1 << mid); mask++) {
            int sum = 0;
            for (int i = 0; i < mid; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum += nums[i];
                }
            }
            leftSums.Add(sum);
        }
        
        leftSums.Sort();
        
        int result = Math.Abs(goal);
        
        // 生成后半部分所有可能的子集和，并与前半部分组合
        for (int mask = 0; mask < (1 << (n - mid)); mask++) {
            int sum = 0;
            for (int i = 0; i < n - mid; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum += nums[mid + i];
                }
            }
            
            int target = goal - sum;
            
            // 二分查找最接近target的值
            int pos = leftSums.BinarySearch(target);
            if (pos < 0) {
                pos = ~pos;
            }
            
            if (pos < leftSums.Count) {
                result = Math.Min(result, Math.Abs(sum + leftSums[pos] - goal));
            }
            if (pos > 0) {
                result = Math.Min(result, Math.Abs(sum + leftSums[pos - 1] - goal));
            }
        }
        
        return result;
    }
}

var minAbsDifference = function(nums, goal) {
    const n = nums.length;
    const mid = Math.floor(n / 2);
    
    // 生成前半部分所有可能的子集和
    const leftSums = [];
    for (let mask = 0; mask < (1 << mid); mask++) {
        let sum = 0;
        for (let i = 0; i < mid; i++) {
            if (mask & (1 << i)) {
                sum += nums[i];
            }
        }
        leftSums.push(sum);
    }
    
    leftSums.sort((a, b) => a - b);
    
    let result = Math.abs(goal);
    
    // 生成后半部分所有可能的子集和，并与前半部分组合
    for (let mask = 0; mask < (1 << (n - mid)); mask++) {
        let sum = 0;
        for (let i = 0; i < n - mid; i++) {
            if (mask & (1 << i)) {
                sum += nums[mid + i];
            }
        }
        
        const target = goal - sum;
        
        // 二分查找最接近target的值
        let left = 0, right = leftSums.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (leftSums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if (left < leftSums.length) {
            result = Math.min(result, Math.abs(sum + leftSums[left] - goal));
        }
        if (left > 0) {
            result = Math.min(result, Math.abs(sum + leftSums[left - 1] - goal));
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(2^(n/2) × log(2^(n/2))) = O(2^(n/2) × n/2)
空间复杂度O(2^(n/2))

其中 n 是数组长度。空间复杂度主要用于存储前半部分的所有子集和。

相关题目