题目
给你一个长度为 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
-107 <= nums[i] <= 107
折半查找后二分
时间复杂度
O(2nlog2n)。
变量解释
| vLeft | vLeft[i]表示从前n个数据中选择i个数的和，记录所有可能 |
| vRight | 类似，记录的是右边 |
分析
如果从左边选择i个数，那么需要从右边选择n-i个数。假定从左边i个数的和是n1，右边选择n-i个数的和为n2。枚举n1，从v2中选择第一个大于等于n2的数和第一个小于n2的数。iTotal 是nums的和。
n1+n2= iTotal-n1-n2 => n2 =iTotal/2 - n1
iTotal要分奇数和偶数分别处理。我们将所有数都乘以2,iTotal就必定是偶数了。
注意
不要忘记
v[0].emplace_back(0);
代码
核心代码
class Solution { public: int minimumDifference(vector<int>& nums) { const int iTotal = std::accumulate(nums.begin(), nums.end(), 0); int n = nums.size() / 2; vector<vector<int>> vLeft(n + 1), vRight(n + 1); auto Build = [&n](vector<vector<int>>& v,int* p, int len) { v[0].emplace_back(0); for (int i = 0; i < len; i++) { for (int j = n; j >= 1 ; j--) { for (const auto& num : v[j - 1]) { v[j].emplace_back(num + p[i] * 2); } } } }; Build(vLeft, nums.data(), n); Build(vRight, nums.data()+n, n); int iRet = INT_MAX; for (int i = 0; i <= n; i++) { auto& v1 = vLeft[i]; auto& v2 = vRight[n - i]; sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); for (const auto& n1 : v1) { auto it = std::upper_bound(v2.begin(), v2.end(),iTotal- n1); if (v2.end() != it) { iRet = min(iRet, *it + n1 - iTotal); } if (v2.begin() != it) { iRet = min(iRet, iTotal - n1 - *(std::prev(it))); } } } return iRet; } };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector nums; int res; { nums = { 3,9,7,3 }; Solution slu; auto res = slu.minimumDifference(nums); Assert(2, res); } { nums = { -36,36 }; Solution slu; auto res = slu.minimumDifference(nums); Assert(72, res); } { nums = { 2,-1,0,4,-2,-9 }; Solution slu; auto res = slu.minimumDifference(nums); Assert(0, res); }
//CConsole::Out(res);
}
2023年2月旧版
class Solution { public: int minimumDifference(vector& nums) { m_c = nums.size() / 2; vectorunordered_set> vSetSumsLeft, vSetSumsRight; std::vector v1( nums.begin(), nums.begin() + m_c); CalSumSet(vSetSumsLeft, v1); std::vector v2(nums.begin() + m_c, nums.end()); CalSumSet(vSetSumsRight,v2 ); int iTotal = std::accumulate(nums.begin(), nums.end(), 0); int iMin = INT_MAX; for (int i = 0; i <= m_c; i++ ) { std::vector v1(vSetSumsLeft[i].begin(), vSetSumsLeft[i].end()); std::vector v2(vSetSumsRight[m_c - i].begin(), vSetSumsRight[m_c - i].end()); std::sort(v1.begin(), v1.end()); std::sort(v2.begin(), v2.end()); auto it = v1.begin(); auto ij = v2.rbegin(); while ((it != v1.end()) && (ij != v2.rend())) { int iDiff = iTotal - (*it + *ij) * 2; iMin = min(iMin, abs(iDiff)); if (iDiff > 0) { it++; } else { ij++; } } } return iMin; } static void CalSumSet(vector& vSetSums,vector& nums) { int c = nums.size() ; vSetSums.resize(c + 1); vSetSums[0].insert(0); for (const auto& n : nums) { vector dp = vSetSums; for (int i = 0; i < c; i++) { for (auto it : vSetSums[i]) { dp[i + 1].insert(it + n); } } vSetSums.swap(dp); } }
int m_c;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
