Meet in middle!

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

思路：
由于输入规模为40，直接枚举整个数组显然会超时，但是如果只有一半规模就没有问题！
故考虑将整个数组分成两半来考虑。
折半 + 二进制枚举 + 排序 + 二分

  1. class Solution {
  2.     public int minAbsDifference(int[] nums, int goal) {
  3.         int n = nums.length / 2, m = nums.length - n;
  4.         List<Integer> list = new ArrayList<>();
  5.         for (int i = 0; i < 1 << n; i++) {
  6.             int sum = 0;
  7.             for (int j = 0; j < n; j++) {
  8.                 if ((i >> j & 1) == 1)
  9.                     sum += nums[j];
  10.             }
  11.             list.add(sum);
  12.         }
  13.         Collections.sort(list);
  15.         int min = Integer.MAX_VALUE;
  16.         for (int i = 0; i < 1 << m; i++) {
  17.             int sum = 0;
  18.             for (int j = 0; j < m; j++) {
  19.                 if ((i >> j & 1) == 1)
  20.                     sum += nums[j + n];
  21.             }
  22.             int l = 0, r = list.size() - 1;
  23.             while (l < r) {
  24.                 int mid = l + (r - l >> 1);
  25.                 if (list.get(mid) + sum < goal)
  26.                     l = mid + 1;
  27.                 else
  28.                     r = mid;
  29.             }
  30.             if (list.get(l) + sum - goal == 0)
  31.                 return 0;
  32.             min = Math.min(min, Math.abs(list.get(l) + sum - goal));
  33.             if (l - 1 >= 0)
  34.                 min = Math.min(min, Math.abs(list.get(l - 1) + sum - goal));
  35.         }
  36.         return min;
  37.     }
  38. }

805. 数组的均值分割

给定的整数数组 A ，我们要将 A数组 中的每个元素移动到 B数组 或者 C数组中。（B数组和C数组在开始的时候都为空）
返回true ，当且仅当在我们的完成这样的移动后，可使得B数组的平均值和C数组的平均值相等，并且B数组和C数组都不为空。
示例:
输入:
[1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

注意:

  • A 数组的长度范围为 [1, 30].
  • A[i] 的数据范围为 [0, 10000].

思路：
其它做法
1755的进阶，需要转换一下思路

总和 个数
A S N
B S1 l1
C S2 l2

S / N = S1 / l1 = s2 / l2 = avg
数组A中每个数都减去一个 avg 有 sum(A) = avg(A) = 0
但是 avg 可能不是整数怎么办？
将数组中的每一个元素乘以数组长度 N 之后再减去 sum(A) 即可

这样问题就转换成了找数组的某个子集，使其和为0，这里因为要将数组分为两部分，所以不能选空集，也不能选全集，特殊处理一下即可。 

  1. class Solution {
  2.     public boolean splitArraySameAverage(int[] nums) {
  3.         int n = nums.length;
  4.         if (n == 1)
  5.             return false;
  6.         int sum = 0;
  7.         for (int x : nums)
  8.             sum += x;
  9.         for (int i = 0; i < n; i++)
  10.             nums[i] = nums[i] * n - sum;
  12.         List<Integer> list = new ArrayList<>();
  13.         int m = n - n / 2;
  14.         n /= 2;
  15.         for (int i = 0; i < 1 << n; i++) {
  16.             int all = 0;
  17.             for (int j = 0; j < n; j++)
  18.                 if ((i >> j & 1) == 1)
  19.                     all += nums[j];
  20.             list.add(all);
  21.         }
  22.         Collections.sort(list);
  25.         for (int i = 1; i < 1 << m - 1; i++) {
  26.             int all = 0;
  27.             for (int j = 0; j < m; j++)
  28.                 if ((i >> j & 1) == 1)
  29.                     all += nums[j + n];
  30.             int idx = binarySearch(list, -all);
  31.             if (list.get(idx) == -all)
  32.                 return true;
  33.         }
  34.         // 右半部分啥也不选，左半部分不能取list.get(0)
  35.         int idx = binarySearch(list, 0);
  36.         if (idx + 1 < list.size() && list.get(idx + 1) == 0)
  37.             return true;
  38.         int sa = 0;
  39.         for (int i = n; i < n + m; i++)
  40.             sa += nums[i];
  41.         //右半部分全选，左半部分不能全选
  42.         idx = binarySearch(list, -sa);
  43.         if (idx + 1 < list.size() && list.get(idx + 1) == -sa)
  44.             return true;
  46.         return false;
  47.     }
  48.     int binarySearch(List<Integer> list, int x) {
  49.         int l = 0, r = list.size() - 1;
  50.         while (l < r) {
  51.             int mid = l + (r - l >> 1);
  52.             if (list.get(mid) < x)
  53.                 l = mid + 1;
  54.             else
  55.                 r = mid;
  56.         }
  57.         return l;
  58.     }
  59. }

方法2：DP解法
二维费用，01背包，恰好，恰好，是否可行

  1. class Solution {
  2.     public boolean splitArraySameAverage(int[] nums) {
  3.         int n = nums.length;
  4.         int sum = 0;
  5.         for (int x : nums)
  6.             sum += x;
  8.         boolean[][] f = new boolean[n + 1][sum + 1];
  9.         f[0][0] = true;
  10.         for (int x : nums) {
  11.             for (int j = n; j >= 1; j--) {
  12.                 for (int k = sum; k >= x; k--) {
  13.                     f[j][k] = (f[j][k] || f[j - 1][k - x]);
  14.                 }
  15.             }
  16.         }
  18.         boolean res = false;
  19.         for (int i = 1; i < n; i++) {
  20.             if ((sum * i) % n == 0) {
  21.                 res = res || f[i][sum * i / n];
  22.             }
  23.         }
  24.         return res;
  25.     }
  26. }

2035. 将数组分成两个数组并最小化数组和的差

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。
请你返回 最小 的数组和之差。

示例 1：
折半二进制/双端dfs - 图1
输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

示例 2：
输入：nums = [-36,36]
输出：72
解释：最优分组方案是分成 [-36] 和 [36] 。
数组和之差的绝对值为 abs((-36) - (36)) = 72 。

示例 3：
折半二进制/双端dfs - 图2
输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。

提示：

  • 1 <= n <= 15
  • nums.length == 2 * n
  • `-107 <= nums[i] <= 107

`

思路：
与1755的区别在于1755是找一个和目标值绝对差最小的子序列
而本题是将整个数组分为两个子序列，考虑他们之间的绝对差最小值
依旧是折半 + 二进制枚举 + 排序 + 二分