快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的值.
数组a[n] ，要找出两个数字 和为x
O(n^2)的算法
很容易我们可以写出这么一个粗暴的算法，那就是两两比较，看有没有符合要求的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//数组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]的元素。这个算法的代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//数组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的大小关系颠倒了表示没有这样的两个数。这个算法的代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//数组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)的时间就可以找到对应的下标了。
支付宝打赏 
微信打赏