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

引用

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

题目：

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

解法：

思路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位置。