Hard

题目描述

给你一个长度为 2 * n 的整数数组 nums。你需要将 nums 分割成两个长度为 n 的数组，使两个数组元素和的绝对差最小。

分割 nums 时，nums 中的每个元素都必须放入两个数组之一。

返回 最小 的绝对差。

示例 1：

输入：nums = [3,9,7,3]
输出：2
解释：最优分割方案是：[3,9] 和 [7,3]。
数组和的绝对差是 abs((3 + 9) - (7 + 3)) = 2 。

示例 2：

输入：nums = [-36,36]
输出：72
解释：最优分割方案是：[-36] 和 [36] 。
数组和的绝对差是 abs((-36) - (36)) = 72 。

示例 3：

输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分割方案是：[2,4,-9] 和 [-1,0,-2] 。
数组和的绝对差是 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。

提示：

  • 1 <= n <= 15
  • nums.length == 2 * n
  • -10^7 <= nums[i] <= 10^7

解题思路

这是一道经典的"中途相遇"（Meet in the Middle）问题。由于 n ≤ 15，直接枚举所有分割方案的时间复杂度为 C(2n, n)，约为 10^8，会超时。

核心思路是将数组分成两半，分别预处理每一半的所有可能子集和，然后组合两半的结果找到最优解。

具体步骤：

  1. 将 nums 分为前 n 个和后 n 个元素
  2. 对每一半，使用位运算枚举所有可能的子集，并按选择的元素个数分组存储
  3. 设目标是让两个数组的和尽可能接近 total/2，对于前半部分选择 k 个元素得到和 s1，我们需要在后半部分选择 (n-k) 个元素，使得 s1 + s2 尽可能接近 total/2
  4. 使用二分查找在后半部分的 (n-k) 个元素的所有可能和中找到最接近 target - s1 的值
  5. 更新答案为 |total - 2*(s1 + s2)|

这种方法将时间复杂度从 O(C(2n,n)) 降低到 O(2^n * n)，在 n=15 时是可以接受的。

关键优化是对每组按和值排序，这样可以用二分查找快速找到最接近目标值的和。

代码实现

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size() / 2;
        int total = accumulate(nums.begin(), nums.end(), 0);
        
        // 生成所有可能的子集和，按选择的元素个数分组
        auto generateSums = [&](int start, int end) {
            vector<vector<int>> sums(n + 1);
            int len = end - start;
            
            for (int mask = 0; mask < (1 << len); mask++) {
                int sum = 0, count = 0;
                for (int i = 0; i < len; i++) {
                    if (mask & (1 << i)) {
                        sum += nums[start + i];
                        count++;
                    }
                }
                sums[count].push_back(sum);
            }
            
            // 排序以便二分查找
            for (int i = 0; i <= n; i++) {
                sort(sums[i].begin(), sums[i].end());
            }
            
            return sums;
        };
        
        auto left = generateSums(0, n);
        auto right = generateSums(n, 2 * n);
        
        int ans = abs(total);
        
        for (int i = 0; i <= n; i++) {
            for (int sum1 : left[i]) {
                int target = total / 2 - sum1;
                auto& candidates = right[n - i];
                
                // 二分查找最接近target的值
                auto it = lower_bound(candidates.begin(), candidates.end(), target);
                
                if (it != candidates.end()) {
                    int sum2 = *it;
                    ans = min(ans, abs(total - 2 * (sum1 + sum2)));
                }
                
                if (it != candidates.begin()) {
                    --it;
                    int sum2 = *it;
                    ans = min(ans, abs(total - 2 * (sum1 + sum2)));
                }
            }
        }
        
        return ans;
    }
};

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) // 2
        total = sum(nums)
        
        def generate_sums(arr):
            sums = [[] for _ in range(n + 1)]
            length = len(arr)
            
            for mask in range(1 << length):
                s = 0
                count = 0
                for i in range(length):
                    if mask & (1 << i):
                        s += arr[i]
                        count += 1
                sums[count].append(s)
            
            for i in range(n + 1):
                sums[i].sort()
            
            return sums
        
        left = generate_sums(nums[:n])
        right = generate_sums(nums[n:])
        
        ans = abs(total)
        
        for i in range(n + 1):
            for sum1 in left[i]:
                target = total // 2 - sum1
                candidates = right[n - i]
                
                # 二分查找最接近target的值
                import bisect
                idx = bisect.bisect_left(candidates, target)
                
                if idx < len(candidates):
                    sum2 = candidates[idx]
                    ans = min(ans, abs(total - 2 * (sum1 + sum2)))
                
                if idx > 0:
                    sum2 = candidates[idx - 1]
                    ans = min(ans, abs(total - 2 * (sum1 + sum2)))
        
        return ans

public class Solution {
    public int MinimumDifference(int[] nums) {
        int n = nums.Length / 2;
        int total = nums.Sum();
        
        var GenerateSums = (int[] arr) => {
            var sums = new List<int>[n + 1];
            for (int i = 0; i <= n; i++) {
                sums[i] = new List<int>();
            }
            
            int length = arr.Length;
            for (int mask = 0; mask < (1 << length); mask++) {
                int sum = 0, count = 0;
                for (int i = 0; i < length; i++) {
                    if ((mask & (1 << i)) != 0) {
                        sum += arr[i];
                        count++;
                    }
                }
                sums[count].Add(sum);
            }
            
            for (int i = 0; i <= n; i++) {
                sums[i].Sort();
            }
            
            return sums;
        };
        
        var left = GenerateSums(nums.Take(n).ToArray());
        var right = GenerateSums(nums.Skip(n).ToArray());
        
        int ans = Math.Abs(total);
        
        for (int i = 0; i <= n; i++) {
            foreach (int sum1 in left[i]) {
                int target = total / 2 - sum1;
                var candidates = right[n - i];
                
                int idx = candidates.BinarySearch(target);
                if (idx < 0) idx = ~idx;
                
                if (idx < candidates.Count) {
                    int sum2 = candidates[idx];
                    ans = Math.Min(ans, Math.Abs(total - 2 * (sum1 + sum2)));
                }
                
                if (idx > 0) {
                    int sum2 = candidates[idx - 1];
                    ans = Math.Min(ans, Math.Abs(total - 2 * (sum1 + sum2)));
                }
            }
        }
        
        return ans;
    }
}

var minimumDifference = function(nums) {
    const n = nums.length / 2;
    const total = nums.reduce((a, b) => a + b, 0);

    const generateSums = (arr) => {
        const sums = Array.from({length: n + 1}, () => []);
        const length = arr.length;

        for (let mask = 0; mask < (1 << length); mask++) {
            let sum = 0, count = 0;
            for (let i = 0; i < length; i++) {
                if (mask & (1 << i)) {
                    sum += arr[i];
                    count++;
                }
            }
            sums[count].push(sum);
        }

        for (let i = 0; i <= n; i++) {
            sums[i].sort((a, b) => a - b);
        }

        return sums;
    };

    const left = generateSums(nums.slice(0, n));
    const right = generateSums(nums.slice(n));

    let ans = Math.abs(total);

    for (let i = 0; i <= n; i++) {
        for (const sum1 of left[i]) {
            const target = Math.floor(total / 2) - sum1;
            const candidates = right[n - i];

            // 二分查找
            let lo = 0, hi = candidates.length;
            while (lo < hi) {
                const mid = Math.floor((lo + hi) / 2);
                if (candidates[mid] < target) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }

            if (lo < candidates.length) {
                const sum2 = candidates[lo];
                ans = Math.min(ans, Math.abs(total - 2 * (sum1 + sum2)));
            }

            if (lo > 0) {
                const sum2 = candidates[lo - 1];
                ans = Math.min(ans, Math.abs(total - 2 * (sum1 + sum2)));
            }
        }
    }

    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(2^n × n)
空间复杂度O(2^n × n)

其中 n 为数组长度的一半。时间复杂度主要来自于枚举两个子数组的所有可能子集，空间复杂度用于存储所有可能的子集和。

相关题目