微软面试百题011——找数

1.问题描述：

题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。 例如输入数组1、2、4、7、11、15 和数字15。由于4+11=15，因此输出4 和11。

2.解法：

1.首先我们按照升序排序 2.添加头尾指针，sum和代表头尾指针对应的元素的和，如果这个和小于我们要找的数，说明头指针小，应该移动头指针， 如果和比我们所需要的值大，说明尾指针需要左移，知道我们找到合适的两者之和等于我们要找的数

3.代码：

void find(int a[],int num,int pos) { int* head=a; int* tail=a+num-1; int sum=*head+*tail; while(head<tail&&sum!=pos) { if(sum<pos) sum=*(++head)+*tail; else if(sum>pos) sum=*head+*(++tail); } cout<<*head<<'+'<<*tail<<endl; }