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

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

    分析与解法

    这个题目不是很难，也很容易理解。但是要得出高效率的解法，还是需要一番思考的。

    【解法一】

    刚看到这个题目，很容易想到的解法就是穷举：从数组中任意取出两个数字，计算两者之和是否为给定的数字。

    显然其时间复杂度为N（N－1）/2即O（N2）。这个算法很简单，写起来也很容易，但是效率不高。一般在程序设计里面，要尽可能降低算法的时间和空间复杂度，所以需要继续寻找效率更高的解法。

    【解法二】

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

    在一个无序数组中查找一个数的复杂度是O（N），对于每个数字arr[i]，都需要查找对应的Sum-arr[i]在不在数组中，很容易得到时间复杂度还是O（N2）。这和最原始的方法相比没有改进。但是如果能够提高查找的效率，就能够提高整个算法的效率。怎样提高查找的效率呢？

    学过编程的人都知道，提高查找效率通常可以先将要查找的数组排序，然后用二分查找等方法进行查找，就可以将原来O（N）的查找时间缩短到O（log2N）。这样对于每个arr[i]，都要花O（log2N）去查找对应的Sum－arr[i]在不在数组中，总的时间复杂度降低为Nlog2N。当然将长度为N的数组进行排序本身也需要O（Nlog2N）的时间，好在只需要排序一次就够了，所以总的时间复杂度依然是O（Nlog2N）。这样，就改进了最原始的方法。

    到这里，有的读者可能会更进一步地想，先排序再二分查找固然可以将时间从O（N2）缩短到O（log2N），但是还有更快的查找方法：hash表。因为给定一个数字，根据hash映射查找另一个数字是否在数组中，只需用O（1）时间。这样的话，总体的算法复杂度可以降低到O（N），但这种方法需要额外增加O（N）的hash表存储空间。在有的情况下，用空间换时间也并不失为一个好方法。

    【解法三】

    还可以换个角度来考虑这个问题，假设已经有了这个数组的任意两个元素之和的有序数组（长为N2）。那么利用二分查找法，只需用O（2log2N）就可以解决这个问题。当然不太可能去计算这个有序数组，因为它需要O（N2）的时间。但这个思考仍启发我们，可以直接对两个数字的和进行一个有序的遍历，从而降低算法的时间复杂度。

    首先对数组进行排序，时间复杂度为（Nlog2N）。

    然后首先令i＝0，j＝n－1，看arr[i]＋arr[j]是否等于Sum，如果是，则结束。如果小于Sum，则i＝i＋1；如果大于Sum，则j＝j－1。这样只需要在排好序的数组上遍历一次，就可以得到最后的结果，时间复杂度为O（N）。两步加起来总的时间复杂度O（Nlog2N），下面这个程序就利用了这个思想。

    代码清单2－23伪代码

    alt

    它的时间复杂度是O（N）。

    扩展问题

    注意我们题目有一个重要的前提，就是数组中肯定存在这样的一对数字。考虑下面的扩展问题：

    1．如果把这个问题中的“两个数字”改成“三个数字”或“任意个数字”时，你的解是什么呢？

    2．如果完全相等的一对数字对找不到，能否找出和最接近的解？

    3．把上面的两个题目综合起来，就得到这样一个题目：给定一个数N，和一组数字集合S，求S中和最接近N的子集。想继续钻研下去的读者，可以看一看专业书籍中关于NP，NP-Complete的描述。

    面试中很多题目都是给定一个数组，要求返回两个下标的（比如找两个元素，或者找一个子数组）。而相应比较高效的解法，则是先排序，然后在一个循环体里利用两个变量进行反向的遍历，并且这两个变量遍历的方向是不变的，从而保证遍历算法的时间复杂度是O（N）。以后读者再遇到类似的问题，也可以考虑利用两个下标进行遍历。