leetcode面试题 16.21(交换和)–Java语言实现

求：

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

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

示例:

输入: 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

题目链接： https://leetcode-cn.com/problems/sum-swap-lcci/

解：

仔细分析题目条件，如果从A、B两个数组中，分别取出一个数进行交换，交换后A、B的数列和能够相等。那么：

设原数列和分别为sum1，sum2，从A中取出的数为a，从B中取出的数为b。

则：sum1-a+b = sum2-b+a，即sum1-sum2=2(a-b)，显然，A、B两个数组的和之差应该是偶数，否则肯定不存在符合条件的a、b。

在sum1-sum2是偶数的前提下，我们要在A、B数组中找到一对(a,b)，满足a-b=(sum1-sum2)/2。设target=(sum1-sum2)/2，原问题转化为在A、B数组中找一对数差为target的问题。同时，满足差为target的一对数，应该满足大数在和更大的数组中，而小的那个数在和更小的数组中。因此我们需要在程序中判断sum1和sum2的相对大小。

对2个数组排序，然后对和较小的数组，逐个取出元素，判断在和较大的数组中是否存在比该元素大target的元素，如果存在则返回。如果差值不够大，将大数继续加大。如果差值太大，将小数加大，直到遍历完成。如果在遍历过程中都没有找到相应的元素对，则返回空数组。

时间复杂度：O(NlogN)

空间复杂度：O(1)

public int[] findSwapValues(int[] array1, int[] array2) {
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < array1.length; i++) sum1 += array1[i];
    for (int i = 0; i < array2.length; i++) sum2 += array2[i];
    if (((sum1 + sum2) & 1) == 1) return new int[0];
    Arrays.sort(array1);
    Arrays.sort(array2);
    int target = Math.abs(sum1 - sum2) >> 1;
    if (sum1 < sum2) {
        for (int i = 0, j = 0; i < array1.length && j < array2.length; ) {
            if (array1[i] + target == array2[j]) return new int[]{array1[i], array2[j]};
            else if (array1[i] + target < array2[j]) ++i;
            else ++j;
        }
    } else {
        for (int i = 0, j = 0; i < array1.length && j < array2.length; ) {
            if (array2[j] + target == array1[i]) return new int[]{array1[i], array2[j]};
            else if (array2[j] + target < array1[i]) ++j;
            else ++i;
        }
    }
    return new int[0];
}