题目描述
给你一个整数数组 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
算法
(折半枚举,二分查找) $O(n 2^{\frac{n}{2}})$
- 枚举前半个数组所有组合的值,记录在数组 $h$ 中。
- 将 $h$ 数组从小到大排序。
- 枚举另一半数组,对于某个组合 $t$,在另一个数组中二分查找 $goal - t$。找到第一个大于等于 $goal - t$ 的位置 $l$,用 $l$ 和 $l-1$ 两个位置的元素更新答案。
时间复杂度
- 预处理并排序 $h$ 数组的时间为 $O(2^{\frac{n}{2}} \log (2^{\frac{n}{2}})) = O(n 2^{\frac{n}{2}})$$。
- 对于另一半数组的每个组合,需要 $O(\log (2^{\frac{n}{2}}))$ 的时间二分查询。
- 故总时间复杂度为 $O(n 2^{\frac{n}{2}})$。
空间复杂度
- 需要 $O(2^{\frac{n}{2}})$ 的空间存储 $h$ 数组。
C++ 代码
class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
const int n = nums.size();
const int m = n >> 1;
vector<int> h;
for (int s = 0; s < (1 << m); s++) {
int t = 0;
for (int i = 0; i < m; i++)
if (s & (1 << i))
t += nums[i];
h.push_back(t);
}
sort(h.begin(), h.end());
int ans = INT_MAX;
for (int s = 0; s < (1 << (n - m)); s++) {
int t = goal;
for (int i = m; i < n; i++)
if (s & (1 << (i - m)))
t -= nums[i];
int l = 0, r = h.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (h[mid] < t) l = mid + 1;
else r = mid;
}
if (ans > abs(h[l] - t))
ans = abs(h[l] - t);
if (l >= 1 && ans > abs(h[l - 1] - t))
ans = abs(h[l - 1] - t);
}
return ans;
}
};