@TOC

# # 题目描述

Alice and Bob have candy bars of different sizes: A[i] is the size of the i-th bar of candy that Alice has, and B[j] is the size of the j-th bar of candy that Bob has.

Since they are friends, they would like to exchange one candy bar each so that after the exchange, they both have the same total amount of candy. (The total amount of candy a person has is the sum of the sizes of candy bars they have.)

Return an integer array ans where ans[0] is the size of the candy bar that Alice must exchange, and ans[1] is the size of the candy bar that Bob must exchange.

If there are multiple answers, you may return any one of them. It is guaranteed an answer exists.

Example 1:

Input: A = [1,1], B = [2,2]
Output: [1,2]

Example 2:

Input: A = [1,2], B = [2,3]
Output: [1,2]

Example 3:

Input: A = [2], B = [1,3]
Output: [2,3]

Example 4:

Input: A = [1,2,5], B = [2,4]
Output: [5,4]

Note:

1. 1 <= A.length <= 10000
2. 1 <= B.length <= 10000
3. 1 <= A[i] <= 100000
4. 1 <= B[i] <= 100000
5. It is guaranteed that Alice and Bob have different total amounts of candy.
6. It is guaranteed there exists an answer.

# # 代码

1. 求数组 A、数组 B 所有糖果大小的总和；使用 set 保存 B 中的各个元素；
2. 求出两个小朋友手中糖果大小总和相等时的目标 target；
3. 遍历 A 中的每个糖果，求如果把该糖果交换出去，期望 Bob 交换的糖果大小 expect_b。
4. 从 B 的 set 中查找是否包含 expect_b，如果包含则说明 [a, expect_b] 是一种可以满足要求的交换。

class Solution(object):
def fairCandySwap(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: List[int]
"""
sum_A, sum_B, set_B = sum(A), sum(B), set(B)
target = (sum_A + sum_B) // 2
for a in A:
expect_b = target - (sum_A - a)
if expect_b in set_B:
return [a, expect_b]
return []

# # 刷题心得

1. 时间复杂度的估计，要学会根据数据规模，判断应该用什么时间复杂度的算法。
2. 根据时间复杂度寻找合适的算法/数据结构，因此需要牢记算法/数据结构的时间复杂度。
3. set 是一种拿空间换时间的数据结构，能够在 O(1) 的时间内判断某个元素是否存在其中。

# # 日期

2018 年 8 月 24 日 —— Keep fighting! 2018 年 11 月 ９ 日 —— 睡眠可以