题目
快速找出一个包含
n
个整数的数组中所有两个数的组合，让这两个数之和等于一个给定的值sum。输入
sum
和
n
，接着是所有整数，要求输出所有两个数的组合。
分析1
如果直接遍历穷举将会得到O(n2)的时间复杂度。对于每一个元素
array[i]
来说，可以将问题转化为
sum−array[i]
是否在数组中，而如果事先将数组排序则可以利用二分查找来完成，此时算法的时间复杂度为
O(nlog(n)+log(n))=O(nlog(n))
。
另外一个思路同样是将数组排序，接着设置两个指针
i
，j分别从两端向中间遍历数组，如果
array[i]+array[j]=sum
，则
i
后移且j前移；如果
array[i]+array[j]<sum
，则
i
后移j不动；
array[i]+array[j]>sum
，则
i
不动j前移；最终找到所有这样的两个数的组合。这样遍历的依据是，对于
k=0∼i−1
，一定有
array[k]+array[j]≤array[i]+array[j]
，
i
后移表示和递增，而对于l=j 1∼n−1，一定有
array[i]+array[l]≥array[i]+array[j]
，
j
前移表示和递减，从而利用双指针遍历就可以依次找出所有两个数的组合。这样算法的时间复杂度依然为O(nlog(n) n)=O(nlog(n))。
能否让时间复杂度进一步减小呢？利用哈希往往能用空间换取时间。不用排序，将所有整数放入哈希表中，对于每一个元素
array[i]
去查表
sum−array[i]
是否存在，这只需要
O(1)
的时间，从而算法的时间复杂度为
O(n)
，但是对于重复的组合需要额外去记录。
代码1
import java.util.*;
public class Sum2 {
static void sum2bs(
int[] array,
int sum) {
Arrays.sort(array);
int n = array.length;
int remain, pos;
for (
int i =
0; i < n; i++) {
remain = sum - array[i];
pos = binarySearch(array, remain, i);
if (pos != -
1)
System.out.println(array[i] +
" " + remain);
}
}
static int binarySearch(
int[] array,
int target,
int left) {
int i = left, j = array.length -
1;
int mid;
while (i <= j) {
mid = i + (j - i) /
2;
if (array[mid] == target) {
return mid;
}
else if (array[mid] < target) {
i = mid +
1;
}
else {
j = mid -
1;
}
}
return -
1;
}
static void sum2bt(
int[] array,
int sum) {
Arrays.sort(array);
int n = array.length;
int i =
0, j = n -
1;
while (i <= j) {
if (array[i] + array[j] == sum) {
System.out.println(array[i] +
" " + array[j]);
i++;
j--;
}
else if (array[i] + array[j] < sum) {
i++;
}
else {
j--;
}
}
}
static void sum2hash(
int[] array,
int sum) {
int n = array.length;
Set<Integer> set =
new HashSet<>();
for (
int i =
0; i < n; i++) {
set.add(array[i]);
}
int remain;
for (
int i =
0; i < n; i++) {
remain = sum - array[i];
if (set.contains(remain))
System.out.println(array[i] +
" " + remain);
}
}
public static void main(String[] args) {
Scanner sc =
new Scanner(System.in);
int sum = sc.nextInt();
int n = sc.nextInt();
int[] array =
new int[n];
for (
int i =
0; i < n; i++) {
array[i] = sc.nextInt();
}
sum2bs(array, sum);
}
}
扩展
将找出所有两个数的组合改为找出所有三个数的组合，其余不变。
分析2
找三个数可以使用同样的思路，但是使用二分查找和双指针遍历就会有不同的复杂度。考虑到
remain2=sum−array[i]
只能有
n
个值，对于每个remain2可以转化为找和为
remain2
的两个数的组合，如果使用二分查找时间复杂度为
O(nlog(n)+n⋅nlog(n))=O(n2log(n))
。但是如果使用双指针遍历，由于找两个数的组合只需要
O(n)
的时间，故时间复杂度为
O(nlog(n)+n⋅n)=O(n2)
。
代码2
import java.util.*;
public class Sum3 {
static void sum3bs(
int[] array,
int sum) {
Arrays.sort(array);
int n = array.length;
int remain1, remain2, pos;
for (
int i =
0; i < n; i++) {
remain2 = sum - array[i];
for (
int j = i; j < n; j++) {
remain1 = remain2 - array[j];
pos = binarySearch(array, remain1, j);
if (pos != -
1)
System.out.println(array[i] +
" " + array[j] +
" " + remain1);
}
}
}
static int binarySearch(
int[] array,
int target,
int left) {
int i = left, j = array.length -
1;
int mid;
while (i <= j) {
mid = i + (j - i) /
2;
if (array[mid] == target) {
return mid;
}
else if (array[mid] < target) {
i = mid +
1;
}
else {
j = mid -
1;
}
}
return -
1;
}
static void sum3bt(
int[] array,
int sum) {
Arrays.sort(array);
int n = array.length;
int remain2, j, k;
for (
int i =
0; i < n; i++) {
remain2 = sum - array[i];
j = i;
k = n -
1;
while (j <= k) {
if (array[j] + array[k] == remain2) {
System.out.println(array[i] +
" " + array[j] +
" " + array[k]);
j++;
k--;
}
else if (array[j] + array[k] < remain2) {
j++;
}
else {
k--;
}
}
}
}
public static void main(String[] args) {
Scanner sc =
new Scanner(System.in);
int sum = sc.nextInt();
int n = sc.nextInt();
int[] array =
new int[n];
for (
int i =
0; i < n; i++) {
array[i] = sc.nextInt();
}
sum3bs(array, sum);
}
}
