文章目录

一、题目
二、解题报告
三、本题小知识
四、加群须知

一、题目

1、题目描述

给你一个长度为 2 * n的整数数组。你需要将 nums分成两个长度为 n的数组，分别求出两个数组的和，并最小化两个数组和之差的绝对值。nums 中每个元素都需要放入两个数组之一。请你返回最小的数组和之差。
样例输入： [3,9,7,3]
样例输出： 2

2、基础框架

C++ 版本给出的基础框架代码如下：

class Solution {
public:
    int minimumDifference(vector<int>& nums) {
        
    }
};

3、原题链接

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

二、解题报告

1、思路分析

$(1)$ 假设所有数的和为 $s u m$ ，要求的是选出一堆数，它们的和为 $x$ ，剩下的数和就是 $s u m - x$ ，要求的是 $∣ (s u m - x) - x ∣$ ，也就是 $∣ s u m - 2 x ∣$ 最小。这是个背包问题，但是数据量太大了，所以动态规划撑不住。
$(2)$ $x$ 如果通过暴力枚举得到，则总共有 $C_{2n}^{n}$ 种情况，当 $n = 15$ 时，数据量太大了。
$(3)$ 我们可以砍掉一半，数组的左边 $n$ 个数，枚举出所有情况；数组的右边 $n$ 个数，枚举出所有情况。进行排序以后，枚举左边的所有情况，并且右边的对应情况中二分找满足条件的解。
$(4)$ 对于数组 [1,2,3,-1,-2,-3]，仔细解释一下：

左边取 3 个
选了 0 个，得到的可能的和如下：0 
选了 1 个，得到的可能的和如下：1 2 3 
选了 2 个，得到的可能的和如下：3 4 5 
选了 3 个，得到的可能的和如下：6 
---
右边取 3 个
选了 0 个，得到的可能的和如下：0 
选了 1 个，得到的可能的和如下：-3 -2 -1 
选了 2 个，得到的可能的和如下：-5 -4 -3 
选了 3 个，得到的可能的和如下：-6

2、算法详解

$(1)$ 将 $2 n$ 个数分成两边，每一边分别 $n$ 个数，如果左边取 $i$ 个数，则右边就需要取 $n - i$ 个数。把左边的 $i$ 个数和右边的 $n - i$ 个数的和加在一起就组成了 $n$ 个数的和 $x$ 。
$(2)$ 可以通过暴力枚举，把左边的 $i$ 个数能够得到的和都存储在vector<int> l[i]数组里，把右边的 $i$ 个数能够得到的和都存储在vector<int> r[i]数组里，通过二进制枚举子集计算这两个数组。

    void getSum(vector<int>& nums, int cnt, int start, vector<int> ans[16]) {
        int i, j;
        for(i = 0; i < (1<<cnt); ++i) {
            int sum = 0;
            for(j = start; j < start + cnt; ++j) {
                if( (1<<(j-start)) & i ) {
                    sum += nums[j];
                }
            }
            ans[ bitCount(i) ].push_back( sum );
        }
        for(i = 0; i <= cnt; ++i) {
            sort(ans[i].begin(), ans[i].end());                                
            ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
        }
    }
    
    getSum(nums, n, 0, l);
    getSum(nums, n, n, r);

$(3)$ l[i][j]代表了左边 $n$ 个数取 $i$ 个数，它的和等于 l[i][j]，则右边必须取 n-i个数，也就是要去r[n-i][...]里面找一个满足条件的值。什么条件呢？对于 l[i][j] + r[n-i][...]就是我们之前提到的 x，于是问题转变成 | sum - 2*(l[i][j] + r[n-i][...]) |的最小值。
$(4)$ l[i][j]可以通过枚举得出，所以是常量，我们就把它定义为val，sum可以预处理所有的和，也是常量。只有r[n-i][...]是一个变量，并且r[n-i]是一个单调递增的数组。
$(5)$ 我们考虑一个函数：
$y = s u m - 2 * (v a l + x)$
随着 $x$ 的增加，函数单调递减，所以是一个单调递减函数。当这个函数和 $x$ 轴有交点的时候，由于绝对值一定是大于等于零，所以在函数图像上，后面那部分小于等于零的部分，会绕着 $x$ 轴进行翻转，于是这个函数就变成了一个有极小值的函数，直接三分求解。

3、时间复杂度

最坏时间复杂度 $O(2^{\frac{n}{2}}log_{3}{2^{\frac{n}{2}}})$ ，所以大概时间复杂度就是 $O(n2^n)$ 。

4、代码详解

class Solution {
    int bitCount(int x) {
        int cnt = 0;
        while(x) {
            x &= (x - 1);
            ++cnt;
        }
        return cnt;
    }


    void getSum(vector<int>& nums, int cnt, int start, vector<int> ans[16]) {
        int i, j;
        for(i = 0; i < (1<<cnt); ++i) {
            int sum = 0;
            for(j = start; j < start + cnt; ++j) {
                if( (1<<(j-start)) & i ) {      // i表示一个集合，前面的左移部分，表示第 j 个元素是否被选取
                    sum += nums[j];
                }
            }
            ans[ bitCount(i) ].push_back( sum );
        }
        for(i = 0; i <= cnt; ++i) {
            sort(ans[i].begin(), ans[i].end());                                 // 排序
            ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());   // 去重

            //printf("选了 %d 个，得到的可能的和如下：\n", i);
            /*for(j = 0; j < ans[i].size(); ++j) {
                printf("%d ", ans[i][j]);
            }*/
            //puts("");
        }
        //puts("---");
    }

    int f(int sum, int val, int x) {
        return abs(sum - 2*val - 2*x);
    }

    // | sum - 2*(val + a[...]) | 的最小值
    int get(int sum, int val, vector<int>& a) {
        // 在 r 里面找到一个值，使得  |sum - 2(val + a[i])| 的值最小
        int l = 0;
        int ret = 1000000000;
        int r = a.size() - 1;
        while(l <= r) {
            int lmid = (2*l + r) / 3;
            int rmid = (l + r*2) / 3;
            int lans = f(sum, val, a[lmid]);
            int rans = f(sum, val, a[rmid]);
            if(lans <= rans) {
                r = rmid - 1;
            }else {
                l = lmid + 1;
            }

            ret = min(ret, lans);
            ret = min(ret, rans);
        }
        return ret;
    }

public:
    int minimumDifference(vector<int>& nums) {
        int n2 = nums.size();
        int n = n2 / 2;
        int i, j;
        int sum = 0;
        vector<int> l[16], r[16];
        for(i = 0; i < nums.size(); ++i) {
            sum += nums[i];
        }
        //printf("左边 %d 个\n", n);
        getSum(nums, n, 0, l);
        //printf("右边 %d 个\n", n);
        getSum(nums, n, n, r);

        int ans = 1000000000;
        for(i = 0; i <= n; ++i) {
            for(j = 0; j < l[i].size(); ++j) {
                // l[i][j]   代表了 左边 n 个数取 i 个数，它的和等于 l[i][j]
                // 则右边必须取  n-i 个数， 也就是要去   r[n-i][...] 里面找
                // 对于 l[i][j] + r[n-i][...] 就是我们之前提到的 x
                // 问题转变成   | sum - 2*(l[i][j] + r[n-i][...]) |  的最小值

                ans = min(ans,  get(sum, l[i][j], r[n-i]) );
            }   
        }

        return ans;
    }
};

三、本题小知识

任何复杂的问题，转换成函数以后，就能逐渐抽丝剥茧，揭露真相。

四、加群须知

相信看我文章的大多数都是「大学生」，能上大学的都是「精英」，那么我们自然要「精益求精」，如果你还是「大一」，那么太好了，你拥有大把时间，当然你可以选择「刷剧」，然而，「学好算法」，三年后的你自然「不能同日而语」。
那么这里，我整理了「几十个基础算法」的分类，点击开启：

?《算法入门指引》?
如果链接被屏蔽，或者有权限问题，可以私聊作者解决。

大致题集一览：
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

为了让这件事情变得有趣，以及「照顾初学者」，目前题目只开放最简单的算法「枚举系列」（包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有一半成员刷完「枚举系列」的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「夜深人静写算法」专家团的一员。
不要小看这个专家团，三年之后，你将会是别人望尘莫及的存在。如果要加入，可以联系我，考虑到大家都是学生，没有「主要经济来源」，在你成为神的路上，「不会索取任何」。
?联系作者，或者扫作者主页二维码加群，加入刷题行列吧?

?让天下没有难学的算法?
C语言免费动漫教程，和我一起打卡！?《光天化日学C语言》?
让你养成九天持续刷题的习惯?《九日集训》?
入门级C语言真题汇总?《C语言入门100例》?
组团学习，抱团生长?《算法零基础100讲》?
几张动图学会一种数据结构?《画解数据结构》?
竞赛选手金典图文教程?《夜深人静写算法》?

原文链接：https://blog.csdn.net/WhereIsHeroFrom/article/details/124031271