class Solution {
public:
int minAbsDifference(vector<int>& nums, int goal) {
}
};
1755. 最接近目标值的子序列和
给你一个整数数组 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原站题解
python3 解法, 执行用时: 1632 ms, 内存消耗: 158.7 MB, 提交时间: 2023-09-25 15:44:36
class Solution:
def minAbsDifference(self, nums: List[int], goal: int) -> int:
n = len(nums)
def state_compress(lst):
m = len(lst)
bit = {1<<i: lst[i] for i in range(m)}
dp=[0]*(1<<m)
for i in range(1, 1<<m):
dp[i]=dp[i^i&-i]+bit[i&-i]
return sorted(list(set(dp)))
pre = state_compress(nums[:n//2])
post = state_compress(nums[n//2:])
ans = abs(goal)
i = 0
j = len(post)-1
while i < len(pre) and j >= 0:
ans = min(ans, abs(goal-pre[i]-post[j]))
if not ans:
return ans
if pre[i]+post[j] > goal:
j -= 1
elif pre[i]+post[j] < goal:
i += 1
return ans
# dfs版本
def minAbsDifference2(self, nums: List[int], goal: int) -> int:
from sortedcontainers import SortedList
def check(lst):
m = len(lst)
res = set()
def dfs(pre, i):
if i == m:
res.add(pre)
return
dfs(pre, i + 1)
dfs(pre + lst[i], i + 1)
return
dfs(0, 0)
return SortedList(list(res))
n = len(nums)
left = check(nums[:n // 2])
right = check(nums[n // 2:])
a, b = len(left), len(right)
ans = abs(goal)
i = 0
j = b - 1
while i < a and j >= 0:
cur = left[i] + right[j] - goal
if abs(cur) < ans:
ans = abs(cur)
if cur > 0:
j -= 1
elif cur < 0:
i += 1
else:
break
return ans
python3 解法, 执行用时: 1896 ms, 内存消耗: 112.4 MB, 提交时间: 2023-09-25 15:43:42
class Solution:
def minAbsDifference(self, nums: List[int], goal: int) -> int:
ans=float('inf') ###### 初始化
def flat(array,pos,flat_array):
'''
param..
array: 原数组
pos 当前位置
flat_array : 当前枚举数组的结果
'''
if pos>len(array)-1:
return flat_array
temp=flat_array+[ele+array[pos] for ele in flat_array]
return flat(array,pos+1,temp)
mid=(len(nums))//2 ### 取一半
left=flat(nums[:mid],0,[0]) #### 初始应加入 [0] 作为不选元素时候的子序列总和
right=flat(nums[mid:],0,[0])
left=sorted(left)
right=sorted(right,reverse=True)
left_id=0
right_id=0
####### 双指针
while(left_id<len(left) and right_id<len(right)):
cur=left[left_id]+right[right_id]
ans=min(abs(cur-goal),ans)
if cur>goal:
right_id+=1
elif cur<goal:
left_id+=1
else:
return 0
return ans
java 解法, 执行用时: 310 ms, 内存消耗: 48.1 MB, 提交时间: 2023-09-25 15:42:21
class Solution {
int point = 0; // 数组数据组合的指针（表示数组的下标）
public int minAbsDifference(int[] nums, int goal) {
int mid = nums.length >> 1;
point = 0;
// 数据{ 5, -7, 3, 5 }==>左侧[5,-7] 右侧[5,-2]
// 保存所有左侧数据的组合==>[0, -7, 5, -2] 左侧数据为(5,-7)
int[] l = new int[1 << mid];
// 保存右侧所有数据的组合==>[0, 5, 3, 8] 右侧数据为(5,-2)
int[] r = new int[1 << (nums.length - mid)];
dfs(nums, 0, mid - 1, 0, l); // 枚举左侧所有组合
point = 0;// 指针归0
dfs(nums, mid, nums.length - 1, 0, r);// 枚举右侧所有组合
int ans = Integer.MAX_VALUE;
Arrays.sort(l);
Arrays.sort(r);
int left = 0, right = r.length - 1;
//组合左侧数据与右侧数据
while (left < l.length && right >= 0) {
int t = l[left] + r[right]; //临时保存左侧数据与右侧数据的组合
ans = Math.min(ans, Math.abs(t - goal));//更改答案
if (t > goal) right--;
else left++;
}
return ans;
}
/**
* @param nums 题目给出的数组
* @param start 数组的开始位置
* @param end 数组的结束位置
* @param sum 保存左侧组合的和（sum）
* @param arr 保存数组组合的和
*/
private void dfs(int[] nums, int start, int end, int sum, int[] arr) {
arr[point++] = sum;
for (int i = start; i <= end; i++) {
dfs(nums, i + 1, end, sum + nums[i], arr);
}
}
}
golang 解法, 执行用时: 772 ms, 内存消耗: 21.6 MB, 提交时间: 2023-09-25 15:40:59
func minAbsDifference(nums []int, goal int) int {
n := len(nums)
half1 := getAllSubSeqSum(nums[:n/2])
half2 := getAllSubSeqSum(nums[n/2:])
sort.Ints(half2)
res := abs(goal)
for _, num := range half1 {
index := largestElementLessThanTarget(half2, goal-num)
for offset := 0; offset <= 1; offset++ {
if 0 <= index+offset && index+offset < len(half2) {
res = min(res, abs(goal-num-half2[index+offset]))
}
}
}
return res
}
func abs(num int) int {
if num < 0 {
return -num
}
return num
}
func largestElementLessThanTarget(nums []int, target int) int {
if nums[0] >= target {
return -1
}
l, r := 0, len(nums)-1
for l+1 < r {
mid := (l + r) / 2
if nums[mid] < target {
l = mid
} else {
r = mid
}
}
if nums[r] < target {
return r
}
return l
}
func getAllSubSeqSum(nums []int) []int {
n := len(nums)
res := make([]int, 1<<n)
for i := 0; i < (1 << n); i++ {
for j := 0; j < n; j++ {
if (1<<j)&i != 0 {
res[i] += nums[j]
}
}
}
return res
}
func min(integers ...int) int {
res := 0x7fffffff
for _, i := range integers {
if res > i {
res = i
}
}
return res
}
golang 解法, 执行用时: 468 ms, 内存消耗: 9.9 MB, 提交时间: 2023-09-25 15:40:07
var q [10000010]int
var cnt int
var ans int
func dfs1(nums []int,index,sum int){
if index==(len(nums)+1)/2{
q[cnt]=sum
cnt++
return
}
dfs1(nums,index+1,sum)
dfs1(nums,index+1,sum+nums[index])
}
func dfs2(nums []int,index,sum,goal int){
if index==len(nums){
l,r:=0,cnt-1
for l<r{
mid:=(l+((r-l)+1)>>1)
//mid:=l+r+1>>1
if q[mid]+sum<=goal{
l=mid
}else{
r=mid-1
}
}
ans=min(ans,abs(q[r]+sum-goal))
if r+1<cnt{
ans=min(ans,abs(q[r+1]+sum-goal))
}
//fmt.Println(q[r],r,ans)
return
}
dfs2(nums,index+1,sum,goal)
dfs2(nums,index+1,sum+nums[index],goal)
}
func min(i,j int)(int){
if i<j{
return i
}
return j
}
func abs(x int)(int){
if x<0{
return -x
}
return x
}
func minAbsDifference(nums []int, goal int) int {
cnt=0
ans=math.MaxInt32
dfs1(nums,0,0)
sort.Ints(q[:cnt])
//fmt.Println(q[:cnt])
dfs2(nums,(len(nums)+1)/2,0,goal)
return ans
}