Pairs with Sum: Design an algorithm to find all pairs of integers within an array which sum to a specified value.
Hints: #548, #597, #644, #673
解法1
可以用暴力破解，两个循环来做但是这样不好。
可以这么西靠，如果给定一个sum，然后取数组中的一个a，那么就是看这个数组中是否存在元素=sum - a。
我们可以把数组中的元素都放到一个Set里，那么就可以很方便的判断“数组中是否存在元素=sum - a”。
有一点要注意的是如果数组中存在重复元素，比如：
1
2
3
4
5
6
7
8
9
|
sum: 4
array: 2, 2, 1, 3
result: {2, 2}, {1, 3}
如果array是: 2, 1, 3
result: {1, 3}
如果array是: 1, 3, 1, 3
result: {1, 3}
|
还要注意不要出现重复结果，比如上面的{1, 3}和{3, 1}就是属于重复结果。
我们可以做一个Map，存放的是元素 -> 计数来解决重复元素的问题。同时用如果构成pair，那么就从Map中去掉这两个元素来解决重复结果的问题。
代码：
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
|
public void pairSum(int[] array, int sum) {
Map<Integer, Integer> numCounts = makeNumCounts(array);
for (int i = 0; i < array; i++) {
int num = array[i];
int other = sum - num;
if (num == other && numCounts.containsKey(num) && numCounts.get(num) > 1) {
System.out.println("{" + num + "," + num "}");
numCounts.remove(num);
}
if (numCounts.containsKey(other)) {
System.out.println("{" + num + "," + other "}");
numCounts.remove(num);
numCounts.remove(other);
}
}
}
private Map<Integer, Integer> makeNumCounts(int[] array) {
Map<Integer, Integer> result = new HashMap<>();
for (int i = 0; i < array; i++) {
int num = array[i];
Integer count = result.get(num);
if (count == null) {
count = 0;
}
count++;
result.put(num, count);
}
return result;
}
|
解法2
给数组排序，让从两头开始找，如果array[head] + array[tail] < sum，那么head++，否则tail–，代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public void pairSum(int[] array, int sum) {
Arrays.sort(array);
int head = 0;
int tail = array.length - 1;
while (head < tail) {
int s = array[head] + array[tail];
if (s == sum) {
System.out.println("{" + array[head] + "," + array[tail] "}");
head++;
tail--;
} else {
if (s < sum) {
head++;
} else {
tail--;
}
}
}
}
|
评论