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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:12 2023-09-13 11:12 Updated    

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

请你返回 最小 的数组和之差。

示例 1：

example-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：

example-3

**输入：** 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

20211010164511.png

解题思路

  1. 如果数组长度特别大，但是数组的和不大 (sum<=10^5)，我们可以使用背包问题的方式来解决，其中dp[i]表示是否能组成容量为 i 的背包
    1049. 最后一块石头的重量 II
    []
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    function lastStoneWeightII(stones: number[]): number {
      const sum = stones.reduce((pre, cur) => pre + cur, 0)
      const volumn = sum >> 1
      // dp[i] 表示若干块石头中能否选出一些组成重量和为 i
      const dp = Array(volumn + 1).fill(false)
      dp[0] = true

      for (let i = 0; i < stones.length; i++) {
        for (let j = volumn; j >= 0; j--) {
          j >= stones[i] && (dp[j] = dp[j] || dp[j - stones[i]])
        }
      }

      const maxWeight = dp.lastIndexOf(true)
      return sum - 2 * maxWeight
    };
  2. 如果数组长度不大(n<=20)，但是数值特别大的话，使用枚举子集的方法。(如果数组长度大于20，例如 40，直接枚举子集2^40会超时,需要折半查找)
    1755. 最接近目标值的子序列和
    5897. 将数组分成两个数组并最小化数组和的差
    步骤：
    1. 将数组分成两部分
    2. 枚举出两个数组的所有子序列和，并排序
    3. 有序的 twoSum 问题 => 双指针

代码

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

[]
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 给你一个整数数组 nums 和一个目标值 goal 。
// 你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal
// 1 <= nums.length <= 40
// -107 <= nums[i] <= 107
// -109 <= goal <= 109
function minAbsDifference(nums: number[], goal: number): number {
  const mid = nums.length >> 1
  const left = getSubArraySumFrom(nums.slice(0, mid)).sort((a, b) => a - b)
  const right = getSubArraySumFrom(nums.slice(mid)).sort((a, b) => a - b)
  return twoSum(left, right, goal)
}

/**
 * @description 计算nums全部子序列和
 * @summary 时间复杂度O(2^n) 
 */
function getSubArraySumFrom(nums: number[]): number[] {
  const n = nums.length
  const res = Array<number>(1 << n).fill(0)

  // 外层遍历数组每个元素
  for (let i = 0; i < n; i++) {
    // 内层遍历从0到外层元素之间的每一个元素
    for (let j = 0; j < 1 << i; j++) {
      res[(1 << i) + j] = res[j] + nums[i]
    }
  }

  return res
}

/**
 * @description
 * 单调不减的数组nums1和nums2分别找到两个数，其和与target的差最小 返回这个最小差值
 */
function twoSum(nums1: number[], nums2: number[], target: number) {
  let l = 0
  let r = nums2.length - 1
  let res = Infinity

  while (l < nums1.length && r > -1) {
    const sum = nums1[l] + nums2[r]
    res = Math.min(res, Math.abs(target - sum))
    if (sum === target) return 0
    else if (sum > target) r--
    else l++
  }

  return res
}

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

[]
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 *
 * @param nums
 * @returns
 * 1 <= n <= 15
   给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，
   并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。
   @description
   1.将原数组中所有数变为两倍。这样可以保证我们的目标值sum/2是一个整数。
   2.枚举出前一半数和后一半数的全部选举情况后再拼接在一起，问题变成了从16组两个元素个数不超过C(7,15)的列表中找出和最接近原来总和一半的方案
 */
function minimumDifference(nums: number[]): number {
  nums = nums.map(num => num * 2)
  const midIndex = nums.length / 2
  const leftSubArraySum = getSubArraySumFrom(nums.slice(0, midIndex))
  const rightSubArraySum = getSubArraySumFrom(nums.slice(midIndex))
  const target = nums.reduce((pre, cur) => pre + cur, 0) / 2

  let res = Infinity
  for (let leftCount = 0; leftCount <= midIndex; leftCount++) {
    const left = leftSubArraySum[leftCount].sort((a, b) => a - b)
    const right = rightSubArraySum[midIndex - leftCount].sort((a, b) => a - b)
    res = Math.min(res, twoSum(left, right, target))
  }
  return res

  /**
   * @description 计算nums的子序列和 下标表示由多少个数组成
   * @summary 时间复杂度O(2^n)
   */
  function getSubArraySumFrom(nums: number[]): number[][] {
    const n = nums.length
    const res = Array.from<number, number[]>({ length: nums.length + 1 }, () => [])
    for (let i = 0; i < 1 << n; i++) {
      const index = count(i)
      let sum = 0
      for (let j = 0; j < n; j++) {
        if (i & (1 << j)) sum += nums[j]
      }
      res[index].push(sum)
    }

    return res

    /**
     * @description
     * 二进制位1的个数
     */
    function count(num: number) {
      let res = 0
      while (num) {
        num &= num - 1
        res++
      }
      return res
    }
  }

  /**
   * @description
   * 单调不减的数组nums1和nums2分别找到两个数，其和与target的差最小 返回这个最小差值
   */
  function twoSum(nums1: number[], nums2: number[], target: number): number {
    let l = 0
    let r = nums2.length - 1
    let res = Infinity

    while (l < nums1.length && r > -1) {
      const sum = nums1[l] + nums2[r]
      res = Math.min(res, Math.abs(target - sum))
      if (sum === target) return 0
      else if (sum > target) r--
      else l++
    }

    return res
  }
}
 Comments
On this page
2035-将数组分成两个数组并最小化数组和的差
  1. 解题思路
  2. 代码