问题描述
给你一个整数数组 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
解题思路
将 \(\texttt{nums}\) 分成左右两部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution:
def minAbsDifference(self, nums: List[int], goal: int) -> int:
n = len(nums)
L = n >> 1
R = n - L
left = [0]
for x in nums[:L]:
left += [x + y for y in left]
right = [0]
for x in nums[L:]:
right += [x + y for y in right]
left.sort()
right.sort()
ans = abs(goal)
L, R = 1 << L, 1 << R
i, j = 0, R - 1
while i < L and j >= 0:
tot = left[i] + right[j]
ans = min(ans, abs(tot - goal))
if tot == goal: break
elif tot > goal: j -= 1
else: i += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
int n = nums.size(), L = n >> 1, R = n - L;
vector<int> left(1 << L), right(1 << R);
for (int i = 0; i < (1 << L); ++i) {
for (int j = 0; j < L; ++j) {
if ((i >> j) & 1) left[i] += nums[j];
}
}
for (int i = 0; i < (1 << R); ++i) {
for (int j = 0; j < R; ++j) {
if ((i >> j) & 1) right[i] += nums[j + L];
}
}
sort(left.begin(), left.end());
sort(right.begin(), right.end());
L = 1 << L, R = 1 << R;
int i = 0, j = R - 1, ans = abs(goal);
while (i < L && j >= 0) {
int sum = left[i] + right[j];
ans = min(ans, abs(sum - goal));
if (sum == goal) break;
else if (sum > goal) --j;
else ++i;
}
return ans;
}
};
|
Python 使用位运算会超时。