寻找数组中和为某一个值的整数对

发表于 | 分类于 |

复习到数据结构的线性表这一章节，书后面有一道题目自己感觉挺好的，所以也就在这里记录一下：

题目

一个长度为N的整形数组A[1…N]， 给定整数X，请设计一个时间复杂度不超过O(nlogn)（原谅我这里不会插入公式）的算法，查找出这个数组中所有两两之和等于X的整数对（每个元素只输出一次）

分析

题目看起来很简单，最简单的做法就是直接让数组的元素两两之间想加比较就能够判断了，但是，题目中有时间复杂度的限制，所以那样做显然就是不行的了。

对于数组的处理，为了获得更好的时间复杂度，我们通常都会首先将数组排序，在这里，我们考虑一下排序，如果数组已经有序，那么我们从大端和小端朝中间查找，就会发现，只需要一个遍历就能够得到结果，而采用快排的时间复杂度刚好是O(nlogn)，所以也就符合了题目要求。

在有序以后的遍历中，有三种情况的考虑：

  • arr[i] + arr[j] < x
    这时小端的数小了，所以 i ++
  • arr[i] + arr[j] > x
    这时大端的数大了，所以 j –
  • arr[i] + arr[j] = x
    这时刚好符合要求，i ++, j –

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
// the start is the first place in the array, and end the last
void qsort(int *arr, int start, int end)
{
	int i, j, middle;
	i = start;
	j = end;
	middle = arr[i];
	if(i < j)
	{
		while(i < j)
		{
			// from right to left, find the first num less than middle
			while(i < j && arr[j] > middle)
				j --;
			if(i < j)
				arr[i ++] = arr[j];
			// from left to right, find the first num less than middle
			while(i < j && arr[i] < middle)
				i ++;
			if(i < j)
				arr[j --] = arr[i];
		}
		arr[i] = middle;
		qsort(arr, start, i - 1);
		qsort(arr, i + 1, end);
	}
}
// to find a pair number that the sum is x
int search(int *arr, int length, int x)
{
	int i = 0, j = length - 1;
	while(i < j)
	{
		if(arr[i] + arr[j] < x)
			i ++;
		else if(arr[i] + arr[j] > x)
			j --;
		else
			printf("%d  %d\n", arr[i ++], arr[j --]);
	}
}
int main()
{
	int arr[5] = {3, 1, 2, 5, 4};
	qsort(arr, 0, 4);
	search(arr, 5, 6);
	return 0;
}

反思

在网上看到说，最低的复杂度能够到达O(n)，采用的方法是将数组中的元素使用哈希表存储下来，存储的复杂度为O(n)，然后对于数组中的每一个元素，去查找X-arr[i]是否在数组中，因为hash表的查找时间复杂度为O(1)，整体的查找时间为O(n)，所以总的时间复杂度为O(n)。

想法挺好的，但是考虑算法、数据结构这些东西都忘完了，也就暂时不实现了，等以后再看看吧。

另外，更惭愧的是快排也不会写了，看来我要加快我的数据结构的复习了。

References