题目:
给定两个整数数组,请交换一对数值(每个数组中取一个数值),使得两个数组所有元素的和相等。
返回一个数组,第一个元素是第一个数组中要交换的元素,第二个元素是第二个数组中要交换的元素。若有多个答案,返回任意一个均可。若无满足条件的数值,返回空数组。
示例:
输入: 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便是要交换两个元素之间的差值,当然如果数组和的差值不能被2整除,就没有满足条件的数值。
将一个数组的元素存入set中,遍历另一个数组,查看其元素和差值相加(相减)是否在集合中。
程序:
class Solution { public int[] findSwapValues(int[] array1, int[] array2) { int sum1 = 0; int sum2 = 0; Set<Integer> set = new HashSet<>(); for(int num:array1){ sum1 += num; set.add(num); } for(int num:array2) sum2 += num; int diff = sum1 - sum2; if(diff % 2 != 0) return new int[]{}; int target = diff / 2; for(int num:array2){ if(set.contains(num + target)){ return new int[]{num + target, num}; } } return new int[]{}; } }