微软等数据结构与算法面试100题 第十四题

第十四题

题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。

要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。

分析：

这道题目比较简单，见代码。说明：代码是给出的所有的组合。

代码：

#include<iostream>using namespace std;bool findSum(int *a, const int length, int sum){bool yesno = false;int startIndex = 0;int endIndex = length-1;if(endIndex < 1) return false;int tempSum;while(startIndex<endIndex){tempSum = a[startIndex] + a[endIndex];if(tempSum>sum){endIndex--;}else if(tempSum<sum){startIndex++;}else{cout<<a[startIndex]<<" "<<a[endIndex]<<endl;yesno = true;startIndex++;}}return yesno;}int main(){int a[10] = {1,2,3,4,5,6,7,8,9,10};cout<<findSum(a,10,10);return 0;}

输出结果为

1 9

2 8

3 7

4 6