本文涉及知识点
折半处理
LeetCode1755. 最接近目标值的子序列和
给你一个整数数组 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
-107 <= nums[i] <= 107
-109 <= goal <= 109
折半处理
pre 记录从nums的前i个元素，选取元素组成子序列的和。
dp 记录从nums的前i+1个元素，选取元素组成子序列的和。
n = nums.length
这样做的时间复杂度是O(2n)，超时了。
dp1记录前n/2个元素组成子序列的和，dp2记录余下的元素组成子序列的和。
对dp2 排序
枚举dp1 各元素x ，在dp2中二分 goal-x：
尝试第一个大于等于 goal-x的数。
尝试最后一个小于 goal-x的数。
时间复杂度： O(m)+O(mlogm) m = 2n/2
代码
核心代码
class Solution { public: int minAbsDifference(vector<int>& nums, int goal) { const int iHalf = nums.size() / 2; vector<int> vNum1 = Sum(nums.data(), iHalf); auto vNum2 = Sum(nums.data() + iHalf, nums.size() - iHalf); sort(vNum2.begin(), vNum2.end()); int iRet = INT_MAX; for (const auto& n : vNum1) { auto it = std::lower_bound(vNum2.begin(), vNum2.end(), goal - n); if (vNum2.end() != it) { iRet = min(iRet, abs(goal - n - *it)); } if (vNum2.begin() != it) { --it; iRet = min(iRet, abs(goal - n - *it)); } } return iRet; } vector<int> Sum(int* p, int n) { vector<int> pre = { 0 }; for (int i = 0; i < n; i++) { vector<int> dp = pre; for (const auto& iPre : pre) { dp.emplace_back(iPre + p[i]); } pre.swap(dp); } return pre; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; int goal; { Solution sln; nums = { 5, -7, 3, 5 }, goal = 6; auto res = sln.minAbsDifference(nums, goal); Assert(0, res); } { Solution sln; nums = { 7,-9,15,-2 }, goal =-5; auto res = sln.minAbsDifference(nums, goal); Assert(1, res); } { Solution sln; nums = { 1,2,3 }, goal = -7; auto res = sln.minAbsDifference(nums, goal); Assert(7, res); } }
2023年2月版
void CreateMaskVector(vector<int>& v,const int* const p,int n ) { const int iMaxMaskNum = 1 << n; v.resize(iMaxMaskNum); for (int i = 0; i < n; i++) { v[1 << i] = p[i]; } for (int mask = 1; mask < iMaxMaskNum ; mask++) { const int iSubMask = mask&(-mask); v[mask] = v[iSubMask] + v[mask-iSubMask]; } } class Solution { public: int minAbsDifference(vector<int>& nums, int goal) { set<int> setLeft, setRight; setLeft.insert(0); setRight.insert(0); int iHalfNum = nums.size()/2; vector<int> vLeft,vRight; CreateMaskVector(vLeft, &*nums.begin(), iHalfNum); CreateMaskVector(vRight, &*nums.begin() + iHalfNum, nums.size() - iHalfNum); std::sort(vLeft.begin(), vLeft.end()); std::sort(vRight.begin(), vRight.end()); int iMin = INT_MAX; auto it = vLeft.begin(); auto ij = vRight.rbegin(); while ((it != vLeft.end()) && (ij != vRight.rend())) { const int tmp = *it + *ij; iMin = min(iMin, abs(tmp - goal)); if (tmp > goal) { ij++; } else { it++; } } return iMin; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
如无特殊说明，本算法用**C++**实现。
