# C#LeetCode刷题之#888-公平的糖果交换（Fair Candy Swap）

1 <= A.length <= 10000
1 <= B.length <= 10000
1 <= A[i] <= 100000
1 <= B[i] <= 100000

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.

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

Output: [1,2]

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

Output: [1,2]

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

Output: [2,3]

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

Output: [5,4]

Note:

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

```public class Program {

public static void Main(string[] args) {
int[] A = { 1, 2, 5 }, B = { 2, 4 };

var res = FairCandySwap(A, B);
ShowArray(res);

A = new int[] { 2 };
B = new int[] { 1, 3 };
res = FairCandySwap2(A, B);
ShowArray(res);

Console.ReadKey();
}

private static void ShowArray(int[] array) {
foreach(var num in array) {
Console.Write(\$"{num} ");
}
Console.WriteLine();
}

private static int[] FairCandySwap(int[] A, int[] B) {
//此解法LeetCode超时未AC
int sumA = A.Sum(), sumB = B.Sum();
int diff = (sumB - sumA) / 2;
for(int i = 0; i < A.Length; i++) {
if(B.Contains(diff + A[i])) {
return new int[] { A[i], diff + A[i] };
}
}
return null;
}

private static int[] FairCandySwap2(int[] A, int[] B) {
var diff = (A.Sum() - B.Sum()) / 2;
var set = new HashSet<int>();
foreach(var num in A) {
set.Add(num);
}
foreach(var num in B) {
if(set.Contains(num + diff)) {
return new int[] { num + diff, num };
}
}
return null;
}

}```

```5 4
2 3```

FairCandySwap中 B.Contains 的执行时间为线性的   ，FairCandySwap2中的 set.Contains 因为使用的是哈希算法，其执行时间为常量时间c。即FairCandySwap的时间复杂度为  ，FairCandySwap2的时间复杂度为：  。