Trace
将数组分成两个数组并最小化数组和的差
传送门：https://leetcode-cn.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/
Problem
给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。
请你返回 最小 的数组和之差。
示例 1：
1
2
3
4
| 输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。
|
示例 2：
1
2
3
4
| 输入：nums = [-36,36]
输出：72
解释：最优分组方案是分成 [-36] 和 [36] 。
数组和之差的绝对值为 abs((-36) - (36)) = 72 。
|
示例 3：
1
2
3
4
| 输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。
|
提示：
1
2
3
| 1 <= n <= 15
nums.length == 2 * n
-10^7 <= nums[i] <= 10^7
|
思路
最接近目标值的子序列和问题，与
https://www.aben.fun/2021/11/02/%E6%9C%80%E6%8E%A5%E8%BF%91%E7%9B%AE%E6%A0%87%E5%80%BC%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97%E5%92%8C/#more
非常类似。
搜索所有子集的时间复杂度较大的时候，可以考虑把原始集合划分成两个相等长度的集合，分别求子集。
这里把原数组划分成$sum1、sum2$两个长度为$n$的集合，分别求出其中所有子集的和（位运算），按组成子集的的元素个数分组。
然后开始合并两个子集，由于固定合并之后的长度为$n$，所以需要遍历$sum1$中组成元素个数从$0-n$的子集（对应$sum2$中为($n-i$)），可以用双指针或者二分求出于$sum/2$的最小差值。
将所有的元素*2是为了避免$sum/2$不是整数。
程序
折半搜索+状态压缩+双指针
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
| class Solution {
public:
int getMin(vector<int>& sum1,vector<int>& sum2,int halfsum){
int Min=0x3f3f3f3f;
int i=0,j=sum2.size()-1;
while(i<sum1.size()&&j>=0){
Min=min(Min,abs(sum1[i]+sum2[j]-halfsum));
if(sum1[i]+sum2[j]>=halfsum){
j--;
}
else{
i++;
}
}
return Min;
}
int minimumDifference(vector<int>& nums) {
int halfsum=0;
for(int i=0;i<nums.size();i++){
halfsum+=nums[i];
nums[i]*=2;
}
int n=nums.size()/2;
vector<vector<int>> sum1(n+1);
vector<vector<int>> sum2(n+1);
for(int i=0;i<(1<<n);i++){
int s=0;
int k=0;
for(int j=0;j<n;j++){
if(i&(1<<j)){
k++;
s+=nums[j];
}
}
sum1[k].push_back(s);
}
for(int i=0;i<(1<<n);i++){
int s=0;
int k=0;
for(int j=0;j<n;j++){
if(i&(1<<j)){
k++;
s+=nums[n+j];
}
}
sum2[k].push_back(s);
}
for(auto& sum:sum1){
sort(sum.begin(),sum.end());
}
for(auto& sum:sum2){
sort(sum.begin(),sum.end());
}
int Min=0x3f3f3f3f;
for(int i=0;i<=n;i++){
Min=min(Min,getMin(sum1[i],sum2[n-i],halfsum));
if(Min==0){
break;
}
}
return Min;
}
};
|
折半搜索+状态压缩+二分
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
| class Solution {
public:
int minimumDifference(vector<int>& nums) {
int halfsum=0;
for(int i=0;i<nums.size();i++){
halfsum+=nums[i];
nums[i]*=2;
}
int n=nums.size()/2;
vector<vector<int>> sum1(n+1);
vector<vector<int>> sum2(n+1);
for(int i=0;i<(1<<n);i++){
int s=0;
int k=0;
for(int j=0;j<n;j++){
if(i&(1<<j)){
k++;
s+=nums[j];
}
}
sum1[k].push_back(s);
}
for(int i=0;i<(1<<n);i++){
int s=0;
int k=0;
for(int j=0;j<n;j++){
if(i&(1<<j)){
k++;
s+=nums[n+j];
}
}
sum2[k].push_back(s);
}
int Min=0x3f3f3f3f;
for(auto& sum:sum2){
sort(sum.begin(),sum.end());
}
for(int i=0;i<sum1.size();i++){
auto x=sum1[i];
auto y=sum2[n-i];
for(auto num:x){
int l=0,r=y.size()-1;
while(l<r){
int mid=(l+r)>>1;
if(num+y[mid]-halfsum>=0){
r=mid;
}
else{
l=mid+1;
}
}
Min=min(Min,abs(num+y[l]-halfsum));
}
}
return Min;
}
};
|
