原文转自:/u013322907/article/details/38300711
题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=15,因此输出 4 和 11。
由于是有序的,可以用双指针来做。第一个指针i指向a[0],第二个j指向a[n-1],
若a[i]+a[j]>v,j--;
若a[i]+a[j]<v,i++;
若a[i]+a[j]=v,结束。
[cpp]view plaincopy#include<iostream>usingnamespacestd;voidfind(inta[],intn,intv){inti=0;intj=n-1;while(i<j){if(a[i]+a[j]<v){i++;}elseif(a[i]+a[j]>v){j--;}else{cout<<a[i]<<"+"<<a[j]<<"="<<v<<endl;return;}}}voidmain(){inta[10]={1,3,6,8,11,13,15,17,20,22};find(a,10,4);system("pause");}
输入一个已经按升序排序过的数组和一个数字 在数组中查找两个数 使得它们的和正好是输入的那个数字。
如果觉得《输入一个已经按升序排序过的数组和一个数字 在数组中查找两个数 使得它们的和正好》对你有帮助,请点赞、收藏,并留下你的观点哦!