欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

在排序数组中查找和为给定值的两个数字

程序员文章站 2022-05-18 17:16:14
...

题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是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;
}

转载于:https://www.cnblogs.com/aLittleBitCool/archive/2011/02/09/1950127.html

推荐阅读