Sum Swap: Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum.
1
2
3
|
EXAMPLE
Input: {4, 1, 2, 1, 1, 2} and {3, 6, 3, 3}
Output: {1, 3}
|
Hints: #545, #557, #564, #577, #583, #592, #602, #606, #635
解法
这个题目的意思是有两个数组，这两个数组的Sum不一样，然后问从这两个数组中各取一个什么数交换一下，能够使得它们的Sum变成一样。
先来看一个公式：
1
2
3
4
5
6
7
|
用A、B代表数组，用a、b代表这两个交换的数，用S代表数组的和
数组A的和可以表示成：(SA - a) + a
数组B的和可以表示成：(SB - b) + b
a、b两个数交换就相当于
(SA - a) + b = (SB - b) + a
可以求得：
b - a = (SB - SA) / 2
|
这样就建立起了a、b两个数字的关系，然后考虑到数组中的都是整数，那么这a和b的差不能为单数
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
public void sumSwap(int[] array1, int[] array2) {
int sum1 = sum(array1);
int sum2 = sum(array2);
int doubleDelta = sum1 - sum2;
if (doubleDelta % 2 == 1) {
// 这个是找不到的
return;
}
int delta = doubleDelta / 2;
Set<Integer> set2 = makeSet(array2);
for (int i = 0; i < array1.length; i++) {
int e1 = array1[i];
int expectedE2 = e1 - delta;
if (set2.contains(expectedE2)) {
System.out.println("" + e1 + "," + e2);
return;
}
}
}
private int sum(int[] array) {
int sum = 0;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}
return sum;
}
private Set<Integer> makeSet(int[] array) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < array.length; i++) {
set.add(array[i]);
}
return set;
}
|
时间复杂度：O(A + B)，M是array1的长度，N是array2的长度
评论