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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 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
-10⁷ <= nums[i] <= 10⁷
-10⁹ <= goal <= 10⁹

# 思路

折半处理

# 解法

class Solution {
    public int minAbsDifference(int[] nums, int goal) {
        int n = nums.length;
        int[] lSet = bit(nums, 0, n/2), rSet = bit(nums, n/2, n);
        Arrays.sort(lSet);
        Arrays.sort(rSet);
        long res = Integer.MAX_VALUE;
        for (int i : lSet) res = Math.min(Math.abs(i - goal), res);
        for (int i : rSet) res = Math.min(Math.abs(i - goal), res);
        int l = 0, r = rSet.length-1;
        long m = -1;
        while (m != 0 && r >= 0 && l < lSet.length) {
            m = lSet[l] + rSet[r] - goal;
            res = Math.min(Math.abs(m), res);
            if (m > 0) {
                r--;
            } else {
                l++;
            }
        }
        return (int) res;
    }
    private int[] bit(int[] nums, int l, int r) {
        int n = r - l, m = (1 << n) - 1;
        int[] res = new int[m+1];
        for (int i = 0; i < n; i++) {
            int p = 1 << i;
            for (int j = 0; j < p; j++) {
                res[p + j] = nums[i + l] + res[j];
            }
        }
        return res;
    }
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java