leetcode面试题：交换和（三种方法实现）

交换和：

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

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

示例：

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

解题思路：

1.首先，先对题目进行理解，交换两个数，使得两个数组的和相等，那么就需要分别把两个数组的和计算出来，如果sum1和sum2的差值为偶数，才有可能可以找到能够交换的数。如果差值为奇数，直接返回空数组。

2.sum1和sum2的差值为偶数时，diff=(sum1-sum2)/2,存在：

sum1-array1[i]+array2[j] = sum2-array2[j]+array1[i]

array1[i]+diff=array2[j]

此时可以满足交换之后，sum1=sum2

方法一：排序+二分查找法

Code:

class Solution {
public:vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {sort(array2.begin(), array2.end());int sum1 = 0, sum2 = 0, m = array1.size(), n = array2.size();for (int & num : array1) sum1 += num;//计算sum1for (int & num : array2) sum2 += num;//计算sum2//如果差值为奇数，不会存在两个数符合题意if ((sum2 -sum1) % 2) return {}; // 两个数组的差值必须是偶数int diff = (sum2 - sum1) / 2;	// 需满足 y = x + diff;for (int i = 0;i < m; i++) {int target = array1[i] + diff;int left = 0, right = n - 1, mid;//对数组2进行二分查找法while (left <= right) {mid = (right + left) >> 1;//找到目标元素if (array2[mid] == target) {return {array1[i], array2[mid]};}else if (array2[mid] > target) right = mid - 1;else left = mid + 1;}}return {};	// 没有找到符合题意的两个数}
};

方法二：排序+双指针

class Solution {
public:vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {sort(array1.begin(), array1.end());     // 对array1排序sort(array2.begin(), array2.end());     // 对array2排序int sum1 = 0, sum2 = 0;for (int num : array1) sum1 += num;   // 数组1求和for (int num : array2) sum2 += num;   // 数组2求和if ((sum1 -sum2) % 2) return {}; // 两个数组的差值必须是偶数int diff = (sum1 - sum2) / 2;   // 需满足 x - y = diffint i = 0, j = 0, m = array1.size(), n = array2.size();while (i < m && j < n) {    // 双指针寻找满足条件的值if (array1[i] - array2[j] < diff) i++;  else if (array1[i] - array2[j] > diff) j++;else return {array1[i], array2[j]};     // 找到符合题意得值，直接返回两个元素即可}return {}; //  未找到符合题意的两个数}
};

方法三：哈希表（因为哈希表可以直接查找，所以就不需要排序了）

class Solution {
public:vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {int sum1 = 0, sum2 = 0;for (int num : array1) sum1 += num;//数组1求和for (int num : array2) sum2 += num;//数组2求和if ((sum1 -sum2) % 2) return {};  // 两个数组的差值必须是偶数//将array2的所有元素放入哈希表中unordered_set<int> arr(array2.begin(), array2.end()); int diff = (sum1 - sum2) / 2; //遍历array1for (int x : array1) {//假定当前array1中要交换的是x，那么在哈希表中找y，如果存在，那就可以交换int y = x - diff; if (setArr2.count(y)) return {x, y};}return {};}
};