`

【面试】快速寻找满足条件(两个数的和为指定值)的两个数

阅读更多
引用
【面试】快速寻找满足条件(两个数的和为指定值)的两个数
题目:

       能否快速找出一个数组中的两个数字,让这两个数字之和等于一个给定的数字,为了简化起见,我们假设这个数组中肯定存在至少一组符合要求的解。

解法:

思路1:

       暴力穷举O(n^2)

思路2:

       对数组预排序O(NlogN),然后遍历该数组,对每一个数a,都进行查找Sum-a在不在数组中。这种查找在二分查找下需要O(logN),所以综上效率为O(NlogN)+O(N)*O(logN)=O(NlogN).

思路3:

       如果在一定的限制条件下,比如说1,数字均为int型,2,此中int型数的范围有一定限制。则可以考虑用hash来获得O(1)的查找效率。方法,首先遍历一遍数组,初始化hash表O(N),然后再次遍历数组,对每一个数字a进行查找SUm-a只需O(1),所以总的效率为:O(N)+O(N)*O(1)=O(N).

思路4:

      首先预排序O(NlogN).然后在一个循环体里使用两个循环变量进行反向遍历,并且这两个变量遍历的方向是不变的,从而保证遍历算法的时间复杂度为O(n)。即令i = 0,j = N-1,这样a[i]+a[j]正好是一个中间数,如果想减小sum的值,就一直缩小j,如果想增加sum的值,就增加i。刚开始一直无法理解这样子一定可以找到这个和么?难道不会漏掉了解得位置。可以这么理解,假如排好序后的数组为1,3,6,a,9,12,17,28,b,35,46  ,那么i最初指向1的位置,j最初指向46的位置,比如所求的是Sum=a+b,a<b,ab在其中数组中某位置上。那么i和j在变化过程中,只考虑i遇到了a或者j遇到了b的时候,必定有一个先遇到,比如i遇到了a,那么这个时候j必定还没指到b,故这是j指到的比b大,从而j减小直到b位置。同理若j先指到了b位置,那么i必定还没指到a(这是我们的前提),然后i现在指到的比a小,故,i增加,直到a位置。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics