面试题 16.21.交换和

1. 题目描述

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

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

示例:

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

标签 数组 哈希表 二分查找 排序

2. 解题

左数组和为lSum, 右数组和为rSum

左边要交换的元素为l， 右边要交换的元素为r

则有lSum-l+r = rSum-r+l -> lSum-rSum = 2(l - r)，可以看出，只有当两个数组和之差为偶数时才有可能交换成功，且l与r必满足l-r=(lSum-rSum)/2

r = l-(lSum-rSum)/2