题目描述
给你一个整数数组 nums
和一个目标值 goal
。
你需要从 nums
中选出一个子序列,使子序列元素总和最接近 goal
。也就是说,如果子序列元素和为 sum
,你需要 最小化绝对差 abs(sum - goal)
。
返回 abs(sum - goal)
可能的 最小值 。
注意,数组的子序列是通过移除原始数组中的某些元素(可能全部或无)而形成的数组。
样例
输入:nums = [5,-7,3,5], goal = 6
输出:0
解释:选择整个数组作为选出的子序列,元素和为 6 。
子序列和与目标值相等,所以绝对差为 0 。
输入:nums = [7,-9,15,-2], goal = -5
输出:1
解释:选出子序列 [7,-9,-2] ,元素和为 -4 。
绝对差为 abs(-4 - (-5)) = abs(1) = 1 ,是可能的最小值。
输入:nums = [1,2,3], goal = -7
输出:7
提示:
1 <= nums.length <= 40
-10^7 <= nums[i] <= 10^7
-10^9 <= goal <= 10^9
算法分析
双端dfs
思路:
如果nums.length <= 20
,则使用单向dfs
做;而如果nums.length <= 40
,则用双端dfs做
双端dfs
主要是通过空间换时间的方式进行操作,假设总共有n
个数值,通过dfs1
计算出n/2
的所有情况,记录下来,再通过dfs2
计算出剩余的情况,再和前半段记录下来的数据进行匹配
具体操作:
- 1、暴力枚举出前
n / 2
的所有情况,存到q[]数组中 - 2、再暴力枚举出剩余的所有情况,假设当前情况的总值是
s
,找到q[]
数组中满足abs(q[i] - s) < goal
的q[i]
的最小值,因此可以在1操作完后,让q[]
数组进行排序- 通过二分查找的方式找到最大的满足
q[i] - s < goal
的q[i]
,更新ans
- 找到
q[i]
后,下一个便是最小的满足q[i + 1] - s > goal
的q[i + 1]
,更新ans
- 通过二分查找的方式找到最大的满足
其中,2^20 = 1,048,576
,数组开到1100000
即可
时间复杂度 $O(2^{\frac{n}{2}} * log\frac{n}{2} + 2^{\frac{n}{2}})$
参考文献
y总
C++ 代码
const int N = 1100010;
int q[N];
class Solution {
public:
int n, cnt, goal, ans;
void dfs1(vector<int>& nums, int u, int s)
{
if(u == n / 2)
{
q[cnt ++] = s;
return ;
}
dfs1(nums, u + 1, s);
dfs1(nums, u + 1, s + nums[u]);
}
void dfs2(vector<int>& nums, int u, int s)
{
if(u == n)
{
int l = 0, r = cnt - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] + s <= goal) l = mid;
else r = mid - 1;
}
ans = min(ans, abs(q[l] + s - goal));
if(l + 1 < cnt)
ans = min(ans, abs(q[l + 1] + s - goal));
return ;
}
dfs2(nums, u + 1, s);
dfs2(nums, u + 1,s + nums[u]);
}
int minAbsDifference(vector<int>& nums, int _goal) {
n = nums.size(), goal = _goal, cnt = 0, ans = INT_MAX;
dfs1(nums, 0, 0);
sort(q, q + cnt);
dfs2(nums, n / 2, 0);
return ans;
}
};