【折半处理二分查找】1755. 最接近目标值的子序列和

本文涉及知识点

折半处理
二分查找算法合集

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
-10⁷ <= nums[i] <= 10⁷
-10⁹ <= goal <= 10⁹

折半处理

pre 记录从nums的前i个元素，选取元素组成子序列的和。
dp 记录从nums的前i+1个元素，选取元素组成子序列的和。
n = nums.length
这样做的时间复杂度是O(2ⁿ)，超时了。

dp1记录前n/2个元素组成子序列的和，dp2记录余下的元素组成子序列的和。
对dp2 排序
枚举dp1 各元素x ，在dp2中二分 goal-x：
尝试第一个大于等于 goal-x的数。
尝试最后一个小于 goal-x的数。
时间复杂度： O(m)+O(mlogm) m = 2^n/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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛