1755. 最接近目标值的子序列和

本文主要是介绍1755. 最接近目标值的子序列和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 1755. 最接近目标值的子序列和

思路

给你一个整数数组 nums 和一个目标值 goal。你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal)。返回 abs(sum - goal) 可能的 最小值。注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
n的数据量是40显然不能使用暴搜，所以我们可以使用双向暴搜 + 双指针来解决这个题目

解题方法

双向广搜 + 双指针

复杂度

时间复杂度:

时间复杂度为$O(2^n\ast log(2^n))$

空间复杂度:

空间复杂度为$O(2^n)$

Code

class Solution {public static int MAXN = 1 << 20;public static int[] lsum = new int[MAXN];public static int[] rsum = new int[MAXN];public static int fill;public static int minAbsDifference(int[] nums, int goal) {int n = nums.length;int min = 0;int max = 0;for (int i = 0; i < n; i++) {if (nums[i] < 0) {min += nums[i];} else if (nums[i] > 0) {max += nums[i];}}if (max < goal) {return Math.abs(max - goal);}if (min > goal) {return Math.abs(min - goal);}Arrays.sort(nums);fill = 0;dfs(nums, 0, n >> 1, 0, lsum);int lsize = fill;fill = 0;dfs(nums, n >> 1, n, 0, rsum);int rsize = fill;Arrays.sort(lsum, 0, lsize);Arrays.sort(rsum, 0, rsize);int ans = Math.abs(goal);for (int i = 0, j = rsize - 1; i < lsize; i++) {while (j > 0 && Math.abs(goal - lsum[i] - rsum[j - 1]) <= Math.abs(goal - lsum[i] - rsum[j])) {j--;}ans = Math.min(ans, Math.abs(goal - lsum[i] - rsum[j]));}return ans;}public static void dfs(int[] nums, int i, int e, int s, int[] sum) {if (i == e) {sum[fill++] = s;} else {int j = i + 1;while (j < e && nums[j] == nums[i]) {j++;}for (int k = 0; k <= j - i; k++) {dfs(nums, j, e, s + k * nums[i], sum);}}}}

这篇关于1755. 最接近目标值的子序列和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---