微软等数据结构与算法面试100题 第十四题
第十四题
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
分析：
这道题目比较简单，见代码。说明：代码是给出的所有的组合。
代码：
[cpp]
#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
补充：软件开发 , C++ ,
