雅乐网

快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的值.

数组a[n] ，要找出两个数字 和为x

O(n^2)的算法

很容易我们可以写出这么一个粗暴的算法，那就是两两比较，看有没有符合要求的

//数组a 元素个数n  两数之和x
int find(int a[], int n, int x)
{
	int i, j;

	for (i = 0; i < n; ++i)
	{
		for (j = i; j < n; ++j)
		{
			if (a[i] + a[j] == x)
				return 1;
		}
	}
	return 0;
}

 O(nlogn)的算法1

观察O(n^2)的算法的第8~12行，这是逐一验证数组中有没有a[j]满足a[i] + a[j] == x 。换一个思路，也就是要查找数组中有没有数值等于x-a[i]的元素。那么我们可以用二分查找来加速搜索。

如果原数组不是有序的，可以使用归并排序，耗时为O(nlogn) 。然后在第5行的for循环中，每次花费O(logn)的时间查找是否有x-a[i]的元素。这个算法的代码如下：

//数组a 元素个数n  两数之和x
int find2(int a[], int n, int x)
{
	int i;

	//归并排序 用时O(nlogn)
	merge_sort(a, 0, n);

	for (i = 0; i < n; ++i) //O(n)
	{
		if (binarysearch(a, x-a[i], i, n) != -1)  //O(logn)
			return 1;
	}
	return 0;
}

  O(nlogn)的算法2

如果数组排好序，我们可以利用这种顺序，以O（n）的时间遍历数组。思路是这样的：设置两个指针i和j，i指向最左边最小的元素，j指向最右边最大的元素，然后判断a[i]+a[j]和x的关系。小于的时候i++，大于的时候j– 。遇见相等就表示找到了。如果i和j的大小关系颠倒了表示没有这样的两个数。这个算法的代码如下：

//数组a 元素个数n  两数之和x
int find3(int a[], int n, int x)
{
	int i, j;
	merge_sort(a, 0, n);

	i = 0;
	j = n-1;

	while (i <= j)
	{
		if (a[i] + a[j] == x)
			return 1;
		else if (a[i] + a[j] < x)
			++i;
		else
			--j;
	}

	return 0;
}

 如果要求输出两个下标

当然排序之后原有的数组的下标就乱了。如果要求输出两个下标值，可以考虑开辟另一个数组作为备份，排序后找到两个值，然后在遍历未排序的原数组，用O(n)的时间就可以找到对应的下标了。