class Solution {
public:
vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {
}
};
面试题 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原站题解
golang 解法, 执行用时: 36 ms, 内存消耗: 6.9 MB, 提交时间: 2022-11-30 21:43:25
func sum(arr []int) int {
var ans int = 0
for _, n := range arr {
ans += n
}
return ans
}
func findSwapValues(array1 []int, array2 []int) []int {
sum1, sum2 := sum(array1), sum(array2)
dif := sum1 - sum2
if dif&1 == 1 {
return []int{}
}
dif >>= 1
hash := make(map[int]struct{})
for _, n := range array2 {
hash[n] = struct{}{}
}
for _, n := range array1 {
tar := n - dif
if _, ok := hash[tar]; ok {
return []int{n, tar}
}
}
return []int{}
}
java 解法, 执行用时: 5 ms, 内存消耗: 50.1 MB, 提交时间: 2022-11-30 21:42:18
class Solution {
public int[] findSwapValues(int[] array1, int[] array2) {
Set<Integer> set = new HashSet<>();
int s = 0;
for(int i : array1)
s += i;
for(int i : array2){
s -= i;
set.add(i);
}
if(s % 2 != 0)
return new int[]{};
for(int i : array1){
if(set.contains(i - s/2))
return new int[]{i , i - s/2};
}
return new int[]{};
}
}
python3 解法, 执行用时: 56 ms, 内存消耗: 19.2 MB, 提交时间: 2022-11-30 21:41:07
class Solution:
def findSwapValues(self, array1: List[int], array2: List[int]) -> List[int]:
sum1, sum2 = sum(array1), sum(array2)
if (sum1 + sum2) % 2:
return []
average = (sum1 + sum2) // 2
gap = sum1 - average
nums2 = set(array2)
for num in array1:
if num - gap in nums2:
return [num, num - gap]
return []