题目描述
给定两个升序排序的有序数组A和B,以及一个目标值x。
数组下标从 0开始。
请你求出满足 A[i]+B[j]=x的数对 (i,j)。
数据保证有唯一解。
样例
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1
算法1-> 双指针
//之前犯的错:两个指针都从前往后扫,但这样数整体是递增的,会漏解
应该一个指针往前扫,另外一个指针往后扫,当a[i]和b[j]最后一次相加大于指定数时(下一次相加就小于指定数了),此时a[i++]和b[j]相加肯定也大于指定数(两个序列都是递增的),所以j–再向前找就不会漏情况
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,num;
cin>>n>>m>>num;
vector<int>a(n),b(m);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<m;i++)cin>>b[i];
for(int i=0,j=m-1;i<n;i++){
while(j>=0&&a[i]+b[j]>num)j--;
if(a[i]+b[j]==num){
cout<<i<<" "<<j<<endl;
break;
}
}
return 0;
}
算法2->二分
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,num;
cin>>n>>m>>num;
vector<int>a(n),b(m);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<m;i++)cin>>b[i];
for(int i=0;i<n;i++){
int c=num-a[i];
int l=0,r=m-1;
while(l<r){
int mid=(l+r)/2;
if(b[mid]>=c)r=mid;
else l=mid+1;
}
if(b[r]==c){
cout<<i<<" "<<r<<endl;
break;
}
}
return 0;
}