Question

题目一：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。

例如输入数组{1、2、4、7、11、15}和数字15。由于4＋11＝15，因此输出4和11。

面试的时候，很重要的一点是应聘者要表现出很快的反应能力。只要想到一个方法，应聘者就可以马上告诉面试官，即使这个方法不一定是最好的。比如这个问题，很多人都能立即想到O（n²）的方法，也就是先在数组中固定一个数字，再依次判断数组中其余的n－1个数字与它的和是不是等于s。面试官会告诉我们这不是最好的办法。不过这没有关系，至少面试官知道我们的思维还是比较敏捷的。

接着我们寻找更好的算法。我们先在数组中选择两个数字，如果它们的和等于输入的s，我们就找到了要找的两个数字。如果和小于s呢？我们希望两个数字的和再大一点。由于数组已经排好序了，我们可以考虑选择较小的数字后面的数字。因为排在后面的数字要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字s了。同样，当两个数字的和大于输入的数字的时候，我们可以选择较大数字前面的数字，因为排在数组前面的数字要小一些。

我们以数组{1、2、4、7、11、15}及期待的和15为例详细分析一下这个过程。首先定义两个指针，第一个指针指向数组的第一个（也是最小的）数字1，第二个指针指向数组的最后一个（也是最大的）数字15。这两个数字的和16大于15，因此我们把第二个指针向前移动一个数字，让它指向11。这个时候两个数字1与11的和是12，小于15。接下来我们把第一个指针向后移动一个数字指向2。此时两个数字2与11的和13，还是小于15。我们再一次向后移动第一个指针，让它指向数字4。数字4、11的和是15，正是我们期待的结果。表6.1总结了在数组{1、2、4、7、11、15}中查找和为15的数对的过程。

表6.1　在数组{1、2、4、7、11、15} 中查找和为15的数对

这一次面试官会首肯我们的思路，于是就可以动手写代码了。下面是一段参考代码：

在上述代码中，ahead为较小的数字的下标，behind为较大的数字的下标。由于数组是排序的，因此较小数字一定位于较大数字的前面，这就是while循环继续的条件是ahead>behind的原因。代码中只有一个while循环从两端向中间扫描数组，因此这种算法的时间复杂度是O（n）。

源代码：

本题完整的源代码详见41_1_TwoNumbersWithSum项目。

测试用例：

- 功能测试（数组中存在和为s的两个数，数组中不存在和为s的两个数）

- 特殊输入测试（表示数组的指针为NULL指针）

看到应聘者比较轻松地解决了问题还有时间剩余，有些面试官喜欢追问和前面问题相关但稍微难一些的问题。比如下面的问题就是一个例子：

题目二：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1＋2＋3＋4＋5＝4＋5＋6＝7＋8＝15，所以结果打印出3个连续序列1～5、4～6和7～8。

有了解决前面问题的经验，我们也考虑用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，bug初始化为2。如果从small到big的序列的和大于s，我们可以从序列中去掉较小的值，也就是增大small的值。如果从small到big的序列的和小于s，我们可以增大big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加small到（1＋s）/2为止。

以求和为9的所有连续序列为例，我们先把small初始化为1，big初始化为2。此时介于small和big之间的序列是{1,2}，序列的和为3，小于9，所以我们下一步要让序列包含更多的数字。我们把big增加1变成3，此时序列为{1,2,3}。由于序列的和是6，仍然小于9，我们接下来再增加big变成4，介于small和big之间的序列也随之变成{1,2,3,4}。由于序列的和10大于9，我们要删去去序列中的一些数字，于是我们增加small变成2，此时得到的序列是{2,3,4}，序列的和正好是9。我们找到了第一个和为9的连续序列，把它打印出来。接下来我们再增加big，重复前面的过程，可以找到第二个和为9的连续序列{4,5}。可以用表6.2总结整个过程。

表6.2　求取和为9的连续序列的过程

形成了清晰的解题思路之后，我们就可以开始写代码了。下面是这种思路的参考代码：

在前面的代码中，求连续序列的和应用了一个小技巧。通常我们可以用循环求一个连续序列的和，但考虑到每一次操作之后的序列和操作之前的序列相比大部分数字都是一样的，只是增加或者减少了一个数字，因此我们可以在前一个序列的和的基础上求操作之后的序列的和。这样可以减少很多不必要的运算，从而提高代码的效率。

源代码：

本题完整的源代码详见41_2_ContinuesSquenceWithSum项目。

测试用例：

- 功能测试（存在和为s的连续序列，如9、100等；不存在和为s的连续序列，如4、0）。

- 边界值测试（连续序列的最小和3）

本题考点：

- 考查思考复杂问题的思维能力。应聘者如果能够通过一两个具体的例子找到规律，解决这个问题就容易多了。

- 考查知识迁移的能力。应聘者面对第二个问题的时候，能不能把解决第一个问题的思路应用到新的题目上，是面试官考查知识迁移能力的重要指标。