数组2007-03-14 15:25:01
阅读4663
评论15
字号：
大中小订阅题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是
O(n)
。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组
1、2、4、7、11、15和数字15。由于4+11=15
，因此输出
4和11。分析：如果我们不考虑时间复杂度，最简单想法的莫过去先在数组中固定一个数字，再依次判断数组中剩下的
n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是
O(n2)。我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字，那太好了，我们找到了要找的两个数字；如果小于输入的数字呢？我们希望两个数字的和再大一点。由于数组已经排好序了，我们是不是可以把较小的数字的往后面移动一个数字？因为排在后面的数字要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字了；同样，当两个数字的和大于输入的数字的时候，我们把较大的数字往前移动，因为排在数组前面的数字要小一些，它们的和就有可能等于输入的数字了。
我们 ...