【面试题】 16.21. 交换和

题目：
给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。

返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。

示例:

输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]

示例:

输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
输出: []

提示：

1 <= array1.length, array2.length <= 100000

答案：

class Solution {
    public int[] findSwapValues(int[] array1, int[] array2) {
        //分别求和，算差多少，然后排序遍历，查看差哪些
        //只有当这个数组和之差为偶数的时候，才有可能通过交换两个数组中的数来达到两个数组和相等的情况，因此首先判断差值是否是偶数，如果不是直接返回空数组就好了。
        //使用哈希表更快一些
        int sum1 = 0, sum2 = 0, len = (array1.length <= array2.length ? array2.length : array1.length);
        HashSet set = new HashSet<>();
        for(int i = 0; i < len; i++){
            if(i < array1.length) {
                sum1 += array1[i];
                set.add(array1[i]);
            }
            if(i < array2.length) sum2 += array2[i];
        }
        int dif = sum2 - sum1;
        if(dif % 2 != 0) return new int[0];
        dif /= 2;
        for (int i : array2) {
            if (set.contains(i - dif)) {
                return new int[]{i - dif, i};
            }
        }
        return new int[0];
    }
}