雅乐网

计算机技术、学习成长

计算机 » 算法 » 数组中找两个数字之和为指定值

数组中找两个数字之和为指定值

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

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

scrn20150130180601

O(n^2)的算法

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

 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]的元素。这个算法的代码如下:

  O(nlogn)的算法2

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

 如果要求输出两个下标

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

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/array_two_sum.html

上一篇:

下一篇:

我要评论

验证码*: 9 + 4 =