微信公众号，欢迎关注
刷题刷题刷题，二叉树，链表，LIS，真是乐趣无穷。
今天在做老师准备的题目，公平分糖果的问题，看起来题目简单好懂，万万没想到我还是太年轻。从此开始了无穷无尽的优化之路，为了下次再犯这样的错误，特此做笔记，一起来看看吧。
正文
题目：
力扣888题.png
输入输出实例：
图片.png
看到题目其实很好懂，无非是两个孩子互换糖果，换完之后大家拥有的糖果总量相同。
0.暴力法（挖坑）
作为一个刷题新手，我总是喜欢叛逆，明知暴力破解不好，但显然暴力破解永远是最好写的。来一手：
class Solution:
def fairCandySwap(self, A, B):
for i in range(len(A)):
for j in range(len(B)):
A[i], B[j] = B[j], A[i]
if sum(A) == sum(B):
return B[j], A[i]
else:
A[i], B[j] = B[j], A[i]
符合人类思考现实问题的逻辑，而且易于理解。不是要交换嘛，那就开始吧
- 把A的第一个和B的第一个交换，然后计算下每人拥有的糖果数量
- 如果相等就直接结束
- 如果不等再换回去 继续向下执行
- 把A的第一个和B的第二个交换，然后计算下每人拥有的糖果数量
- 如果相等就直接结束
- 如果不等再换回去 继续向下执行
.....
- 把A的第二个和B的第一个交换，然后计算下每人拥有的糖果数量
- 如果相等就直接结束
- 如果不等再换回去 继续向下执行
- 把A的第二个和B的第二个交换，然后计算下每人拥有的糖果数量
- 如果相等就直接结束
- 如果不等再换回去 继续向下执行
因为答案保证存在，那么一定会有结果输出。轻轻松松提交，万万没想到。
超时了
来看看最后的测试数据：
服气
也可以理解，暴力法
- 时间复杂度是：
- 空间复杂度是
数据量巨大的时候确实有点难搞，既然暴力法不让玩儿，那就继续头铁优化吧
1.剪枝优化
刷题刷多了我们往往会有这样的前置知识，当有双重循环要做一个外层和内层
的和或者积的时候，我们经常可以简化为一层循环。
为了表述方便，我们这样标记：
- A的糖果总量
- B的糖果总量
- 每人最终分到的糖果数量
这样我们就可以只需要在表面单独循环A，当A交出第个糖果的时候，计算A此时的糖果余量为
,然后去B的糖果里边找有没有等于这一余量的糖果，如果刚好有那么直接交换满足题意。如果没有满足的，证明这个糖果不能交换，那么继续往后遍历直到找到结果。
来看代码：
class Solution:
def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
suma= sum(A)
sumb=sum(B)
averageab = (suma + sumb) / 2
for i in range(len(A)):
currresult=int(averageab - (suma - A[i]))
if currresult in B:
return A[i], currresult
相对于暴力法来说，这里减少了每次交换完再去求的过程,，减少了部分时间。
什么？？？四秒？？这能忍，显然不行，继续优化，头铁。
2.从题目出发
因为我们存在一个计算和的过程，在计算的时候也只涉及到数字的加减，但是如果A中有重复数字呢，诶好像不影响，因为找到一个马上就返回了不影响。诶也不对，假如目前这个不是正确答案，但是在正确答案之前还有很多个与之重复的错误答案，我们是不是浪费了好多时间在这上边。还有B，我们在B中寻找需要的值的时候是不是也是要底层遍历很多重复的错误答案之后才能得到对的。
ok，答案显然浮出水面，去重
python给我们提供了非常棒的去重方法，那就是集合set。这就有人说了，你要用集合，岂不是空间复杂度就高了，因为要建立集合来实现去重。其实大家都这样，一个算法的优秀与否就是要看它的时间复杂度和空间复杂度，我们既然来减少时间，很有可能就得提高空间复杂度，也就是常说的空间换时间。
class Solution:
def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
suma= sum(A)
sumb=sum(B)
averageab = (suma + sumb) / 2
listseta=list(set(A))
listsetb=list(set(B))
for i in range(len(listseta)):
currresult=int(averageab - (suma - listseta[i]))
if currresult in listsetb:
return listseta[i], currresult
来看结果：
很明显，时间减少了，空间变多了。2.66s也不行啊，还是太慢啊。为什么这么慢，其实我们可以分析分析。
- 我们每次拿出A的一个糖果
- 计算A的余量
- 计算A要达到最终的糖果值，还需要多少糖果
- 去B中遍历查找余量
很容易可以看出最终的时间复杂度仍然是：
在计算的数量级上并没有特别实质性的变化，行吧继续头铁。
3. 双指针
我们要充分利用之前已经优化过得方案，即集合去重。在此基础上，我们要想真正把时间复杂度减到线性级别。
我们可以得出
- A的糖果总量
- B的糖果总量
- 每人最终分到的糖果数量
- A要达到条件，就要拿出一个换来另一个，拿出的和换来的差值为
相信你已经有想法了，我们可以直接用while来控制循环
- 首先对
从小到大排个序
- A拿出第一个，B也拿出第一个
- 计算差值
- 如果与
相等那么直接结束循环
- 如果大于
+如果小于
- 如果与
来看代码
def fairCandySwap(self, A, B):
suma = sum(A)
sumb = sum(B)
temp = suma - (suma + sumb) / 2
listseta = list(set(A))
listsetb = list(set(B))
listseta.sort()
listsetb.sort()
i = 0
j = 0
while i < len(listseta) and j < len(listsetb):
if listseta[i] - listsetb[j] == temp:
return listseta[i], listsetb[j]
elif listseta[i] - listsetb[j] > temp:
j += 1
elif listseta[i] - listsetb[j] < temp:
i += 1
来看结果：
0.5s还算舒适，我们可以分析下为什么。其实就是因为这样的遍历使得最坏的时间复杂度来到了,线性，最多遍历A的长度加B的长度次，就结束了。
至此优化结束，时间就是生命，知识就是力量，加油加油。
网友评论