文档介绍：: .
（招聘面试）程序员面试题
精选 : .
程序员面试题精选100(10)－于排序数组中查找和为给定值的俩个数字 题
数组2007-03-1415:25:01466315阅读评论字号：大中小订阅
题目：输入壹个已经按升序排序过的数组和壹个数字，于数组中查找俩个数，使得它们的和正好是输入的那
个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意壹对即可。
例如输入数组1、2、4、7、11、1515。由于4+11=15，因此输出411。 和数字和
分析：如果我们不考虑时间复杂度，最简单想法的莫过去先于数组中固定壹个数字，再依次判断数组中剩下
的n-1O(n个数字和它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是 2)。
我们假设当下随便于数组中找到俩个数。如果它们的和等于输入的数字，那太好了，我们找到了要找的俩个
数字；如果小于输入的数字呢？我们希望俩个数字的和再大壹点。由于数组已经排好序了，我们是不是能够
把较小的数字的往后面移动壹个数字？因为排于后面的数字要大壹些，那么俩个数字的和也要大壹些，就有
可能等于输入的数字了；同样，当俩个数字的和大于输入的数字的时候，我们把较大的数字往前移动，因为
排于数组前面的数字要小壹些，它们的和就有可能等于输入的数字了。
我们把前面的思路整理壹下：最初我们找到数组的第壹个数字和最后壹个数字。当俩个数字的和大于输入的
数字时，把较大的数字往前移动；当俩个数字的和小于数字时，把较小的数字往后移动；当相等时，打完收
工。这样扫描的顺序是从数组的俩端向数组的中间扫描。
问题是这样的思路是不是正确的呢？这需要严格的数学证明。感兴趣的读者能够自行证明壹下。
参考代码：
///////////////////////////////////////////////////////////////////////
//Findtwonumberswithasuminasortedarray
//Output:tureisfoundsuchtwonumbers,otherwisefalse
///////////////////////////////////////////////////////////////////////
boolFindTwoNumbersWithSum
(
intdata[],//asortedarray
unsignedintlength,//thelengthofthesortedarray
intsum,//thesum
int&num1,//thefirstnumber,output