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

Raphael Liu Lv10

给你一个长度为 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-将数组分成两个数组并最小化数组和的差