题目描述
给一个长度是2*n的数组，需要将数组分成两个长度为n的数组
问怎么划分，可以让两个数组和的差的绝对值最小？
| f1-折半枚举+排序+二分 |
基本分析
1.题意怎么转化？两个数组和的差->从nums中选n个数取正号，其余n个数取负号，然后求元素和
2.整个数组最长是30，大概暗示了什么？如果折半，是在状态压缩范围之内的
3.折半处理的思路是什么？把数组元素分成两半left和right，对left和right分别枚举n个元素取正或者负的所有情况，对按照正的个数c分组，分别形成两个字典cntl和cntr。遍历时：遍历cntl中的正数个数c，再遍历cntl[c]中的每个和suml，对这个suml，在cntr[c]中二分去找最接近的数字，两者的差是可能的结果ans
4.二分时候的细节和可能有哪些？这里用了二分1的方法，就是从cntr[c]中去找>=suml的最小值
- 可能cntr[c]的所有值都不满足，这个时候mid=r，用r处的点去比就行了
- 可能找到了合适的l，且l>0, 这个时候l处的值>=suml, l-1处的值<suml, 两个位置都有可能
- 可能找到了合适的l，但l==0，这个时候不存在<suml的数，只比较l处就行
代码
class Solution:
def minimumDifference(self, nums: List[int]) -> int:
def min( x, y):
return x if x<=y else y
n = len(nums) // 2
al = nums[:n]
ar = nums[n:]
cntl = defaultdict(list)
cntr = defaultdict(list)
nmask = 1<<n
for mask in range(nmask):
c = mask.bit_count()
suml, sumr = 0, 0
for j in range(n):
if mask & (1<<j):
suml += al[j]
sumr += ar[j]
else:
suml -= al[j]
sumr -= ar[j]
cntl[c].append(suml)
cntr[c].append(sumr)
for k in cntr.keys():
cntr[k].sort()
ans = float('inf')
for k in cntl.keys():
for suml in cntl[k]:
l, r = 0, len(cntr[k])-1
while l < r:
mid = (l+r)>>1
if cntr[k][mid] >= suml:
r = mid
else:
l = mid+1
# 找到这个位置以后，有几种可能？
# l不满足>=sum_, 但是l已经是最右边，l是一个极值点
# l满足>=sum_,而且l左边还有值，l和l-1处都需要考虑
# l满足>=sum_，但是l左边没有值，只考虑l
if cntr[k][l] < suml:
ans = min(ans, suml - cntr[k][l])
elif cntr[k][l] >=suml and l>0:
ans = min(ans, cntr[k][l]-suml)
ans = min(ans, suml - cntr[k][l-1])
elif cntr[k][l] >=suml and l==0:
ans = min(ans, cntr[k][l] - suml)
if ans == 0 or ans == 1:
return ans
return ans
复杂度
时间：\(设一半的数组长是n，枚举生成cnt[c]需要O(n \cdot 2^n),后面遍历的复杂度不好写，待确认\)
空间：待确认
总结
缩小规模：枚举规模为n的的mask的情况，避免直接对30长度的nums动手（直接动手有没有啥方法）
为啥两边同时找cnt[c]来做差是可行的？举个例子[2,2,0,2,4,0,4,2]。对于前半会取c为3时，候选的和在[2,6]之间，后面c取3时候，候选的和在[2,6,10]之间。对于c=3的意思就是，前半取3个正1负，后半取3个正1负，因为还要做减法，两个和接近相等就是差值最小。这个里差值最小的情况就是1101 和 1110对应。