快速寻找满足条件的两个数

　　在一个数组中能否快速找出两个数字,让这两个数字之和等于一个给定的值——《编程之美》

　　最简单的方法: 穷举法

1 def printInts(arr, sum):
2     size = len(arr)
3     for i in range(size):
4         for j in range(i + 1, size):
5             if (arr[i] + arr[j]) == sum:
6                 print (arr[i], arr[j])

　　算法简单,但效率不高,时间复杂度N(N-1)/2

　　查找法:

　　求两个数字之和,假定给定的和为sum。一个变通的思路，就是对数组中的每个数字arr[i]都判别sum-arr[i]是否在数组中。这样就变成一个查找的算法。

　　既然是查找的方法,为了提高查找效率，首先对数组进行排序。

 1 //这里采用二分查找法
 2 def binarySearch(arr, k):
 3     size = len(arr)
 4     lo = 0
 5     hi = size - 1
 6     while lo <= hi:
 7         mid = (lo + hi) / 2
 8         if k == arr[mid]:
 9             return mid
10         elif k < arr[mid]:
11             hi = mid - 1
12         else:
13             lo = mid + 1
14     return -1
15 
16 def printInts(arr, sum):
17     size = len(arr)
18     for i in range(size):
19         j = binarySearch(arr, sum - arr[i])
20         if j != -1 and i != j:
21             print (arr[i], arr[j])

　　时间复杂度N*log₂N。

　　当然还有更快的方法:hash表,给定一个数字,根据hash映射查找另一个数字是否在数组中，只需o(1)时间，这样的话总体算法复杂度可以降低到0(N)，但是这种方法需要额外增加o(N)的hash表存储空间，也就是空间换时间。

　　二分查找法的改进:

　　换个角度考虑这个问题, 假定已经有了这个数组的任意两个元素之和的有序数组(长为N²)。那么利用o(2log2N)就可以解决这个问题。当然我们不可能去计算这个有序数组，因为需要o(N²)的时间。但这个思考启发我们，可以直接对两个数字的和进行一个有序的遍历，从而降低算法的时间复杂度。

　　首先对数组进行排序，时间复杂度为(Nlog₂N)。

　　算法思路:

　　另i = 0, j = n -1 ，看arr[i] + arr[j]是否等于sum，如果是，则打印出，如果小于sum，则令i = i + 1；如果大于sum，则另j = j - 1。这样只需要在排序好的数组上遍历一次，就可以得到最后的结果，时间复杂度为o(N)，两步加起来时间复杂度o(Nlog₂N)：

 1 def printInts3(arr, sum):
 2     size = len(arr)
 3     i = 0
 4     j = size - 1
 5     while i < j:
 6         s = arr[i] + arr[j]
 7         if s == sum:
 8             print (arr[i], arr[j])
 9         elif s < sum:
10             i = i + 1
11         else:
12             j = j - 1

　　感觉想出这个算法的人脑子肯定很聪明,已经熟练掌握排序和查找的灵活运用与扩展。