将数组分成两个数组并最小化数组和的差

题目

2035. 将数组分成两个数组并最小化数组和的差

---

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。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

题解

方法一：

思路

折半搜索+二分。

注意到数据量极小（n=30），但是每个数的数值范围极大(m=1e9)。

如果数据量不太小（n=1e3），所有数的总和范围不太大(sum(m)=1e3)，可以用01背包解决。时间复杂度$O(n*sum(m))$

这里就利用数据个数极小这一点进行优化。

利用折半搜索和二分查找，将时间复杂度降低到$O(2^{n/2}*log(2^{n/2}))$

具体做法是

将前n/2个数枚举选取的组合，对于选取的一部分a认为是放到第一个数组中，对于没有选取的一部分b认为是放到第二个数组中。

将a个数求和-b个数求和存入有序集合中。

然后再对后n/2个数枚举组合。在有序集合中寻找一个值与之和最靠近0，这可以用二分查找。

代码

class Solution {
public:
    using ll = long long;
    int minimumDifference(vector<int>& nums) {
        int n = nums.size()/2;
        set<ll> st[n+1];
        for (int i=0; i<1<<n; i++) {
            ll cnt = 0, cb = 0;
            for (int j=0; j<n; j++) {
                if (i>>j&1) {
                    cnt += nums[j];
                    cb++;
                } else {
                    cnt -= nums[j];
                }
            }
            st[cb].insert(cnt);
        }
        ll ans = 1e15;
        for (int i=0; i<1<<n; i++) {
            ll cnt = 0, cb = 0;
            for (int j=0; j<n; j++) {
                if (i>>j&1) {
                    cnt += nums[j+n];
                } else {
                    cnt -= nums[j+n];
                    cb++;
                }
            }
            auto it = st[cb].lower_bound(-cnt);
            if (it != st[cb].end()) {
                ans = min(ans, abs(*it+cnt));
            }
            if (it != st[cb].begin()) {
                ans = min(ans, abs(*--it+cnt));
            }
        }
        return ans;
    }
};

方法二：

思路

折半搜索，枚举前n个数的组合情况（选取x个的和减去剩余的n-x个的和cnt）存入第x个平衡树，注意到要将2n长度的数组分割成两个长度为n的数组。第二次枚举时当选取x个负数时，和为cnt，可以在第x个平衡树中二分查找离-cnt最近的数

同理也可以转化为n+1对有序列表，进行n+1次双指针。

代码

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        int n = nums.size();
        long sum =  accumulate(nums.begin(), nums.end(), 0L);
        vector<vector<long>> a(n+1), b(n+1);
        for (int i=0; i<(1<<n/2); i++) {
            long cnt = 0, w = 0;
            for (int j=0; j<n/2; j++) {
                if (i>>j&1) {
                    cnt += nums[j];
                    w++;
                } else {
                    cnt -= nums[j];
                }
            }
            a[w].push_back(cnt);
        }
        long ans = 0x3f3f3f3f;
        for (int i=0; i<(1<<n/2); i++) {
            long cnt = 0, w = 0;
            for (int j=0; j<n/2; j++) {
                if (i>>j&1) {
                    cnt += nums[j+n/2];
                } else {
                    cnt -= nums[j+n/2];
                    w++;
                }
            }
            b[w].push_back(cnt);
        }
        for (int i=0; i<=n; i++) {
            sort(a[i].begin(), a[i].end());
            sort(b[i].begin(), b[i].end());
            int l = 0, r = (int) b[i].size()-1;
            while (l<a[i].size() && r>=0) {
                ans = min(ans, abs(a[i][l] + b[i][r]));
                if (a[i][l] + b[i][r] > 0) r--;
                else l++;
            }
        }
        return ans;
    }
};