888.公平的糖果交换

题目

爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 根糖果棒的大小，B[j] 是鲍勃拥有的第 j 根糖果棒的大小。

因为他们是朋友，所以他们想交换一根糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）

返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。

如果有多个答案，你可以返回其中任何一个。保证答案存在。

示例 1：

输入：A = [1,1], B = [2,2]
输出：[1,2]

示例 2：

输入：A = [1,2], B = [2,3]
输出：[1,2]

示例 3：

输入：A = [2], B = [1,3]
输出：[2,3]

示例 4：

输入：A = [1,2,5], B = [2,4]
输出：[5,4]

提示：

• 1 <= A.length <= 10000
• 1 <= B.length <= 10000
• 1 <= A[i] <= 100000
• 1 <= B[i] <= 100000
• 保证爱丽丝与鲍勃的糖果总量不同。
• 答案肯定存在。

思路

一上来就有了大体的思路：A和B交换的数字的差值，应该是A的总数与B的总数的差值的二分之一，即a - b = (sumA - sumB) / 2。那么就遍历A中的每个数，同时遍历B中的每个数，看是否存在满足上式的数字就行。

上面的方法，对遍历的每个a，都要同时遍历所有b，因此复杂度是O(mn)，m和n分别是数组A和B的长度。

可以利用哈希表的数据结构将复杂度降到线性：

将数组B存到哈希表中，这样对于遍历到的每个数字a，只需要在哈希表中查询是否存在符合条件的b即可。

采用了哈希表后，只需要遍历一次数组A，且哈希表的查询时间复杂度是常数级别的，因此总的时间复杂度降到了O(m+n)！

启发：将数组转换成哈希表，巧妙地利用哈希表的常数时间查询替代线性遍历去优化时间复杂度。

代码

Java中实现哈希表的集合类是HashSet哦～

class Solution {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sumA = 0;
        int sumB = 0;
        for (int a : A) {
            sumA += a;
        }
        HashSet<Integer> bSet = new HashSet<Integer>(); 
        for (int b : B) {
            sumB += b;
            bSet.add(b);
        }
        for (int a : A) {
            int bExpect = a - (sumA - sumB)/2;
            if (bSet.contains(bExpect)) { 
                return new int[]{a, bExpect};
            }
        }
        return new int[]{};
    }
}