交换和
- 难度:Medium
- 题目链接:https://leetcode-cn.com/problems/sum-swap-lcci/
题目描述
给定两个整数数组,请交换一对数值(每个数组中取一个数值),使得两个数组所有元素的和相等。
返回一个数组,第一个元素是第一个数组中要交换的元素,第二个元素是第二个数组中要交换的元素。若有多个答案,返回任意一个均可。若无满足条件的数值,返回空数组。
示例:
输入: 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:
vector<int> findSwapValues(vector<int>& arr1, vector<int>& arr2) {
int sum1 = accumulate(arr1.begin(), arr1.end(), 0);
int sum2 = accumulate(arr2.begin(), arr2.end(), 0);
int diff = sum1 - sum2;
if(abs(diff) % 2 == 1){
return {};
}
unordered_set<int> arr2_set(arr2.begin(), arr2.end());
for(int n: arr1){
int target = n - diff / 2;
if(arr2_set.find(target) != arr2_set.end()){
return {n, target};
}
}
return {};
}
};