题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
感觉这种利用两个指针的使用可以大大提高效率。学到挺多的.........
//在排序数组中查找和为给定值的两个数字
//从数组的两端开始扫,若两数之和小于目标,则头往后进一位,否则尾往前进一位
#include<iostream>
using namespace std;
bool find(int data[],int length,int num,int &ans1,int &ans2){ //o(n)的时间复杂度
int head=0;
int tail=length-1;
while(head!=tail){
int tempsum=data[head]+data[tail];
if(tempsum==num) {ans1=data[head];ans2=data[tail];return true;} //三种情况
if(tempsum<num) head++;
else tail--;
}
return false;
}
int main(void){
int data[]={1,2,4,7,11,15};
int a1=0,a2=0;
if(find(data,6,15,a1,a2)){
cout<<a1<<" "<<a2<<endl;
}
else cout<<"no answer"<<endl;
system("pause");
return 0;
}