题目描述
给定两个升序排序的有序数组 A
和 B,以及一个目标值 x。
数组下标从 0开始。
请你求出满足 A[i]+B[j]=x的数对 (i,j)。
数据保证有唯一解
样例
//算法1 双指针法 O(n)时间复杂度
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
int n,m,x;
int A[N];
int B[N];
int main()
{
cin>>n>>m>>x;
for(int i=0;i<n;i++)
{
cin>>A[i];
}
for(int j=0;j<m;j++)
{
cin>>B[j];
}
for(int i=0,j=m-1;i<n;)
{
while(A[i]+B[j]>x)
{
j--;
}
while(A[i]+B[j]<x)
{
i++;
}
if(A[i]+B[j]==x)
{
cout<<i<<" "<<j;
break;
}
}
return 0;
}
//算法2 二分查找 O(nlogn)时间复杂度
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
int n,m,x;
int A[N];
int B[N];
int main()
{
cin>>n>>m>>x;
for(int i=0;i<n;i++)
{
cin>>A[i];
}
for(int j=0;j<m;j++)
{
cin>>B[j];
}
for(int i=0;i<n;i++)
{
int l=-1,r=m;
while(l+1<r)
{
int mid=l+r>>1;
if(A[i]+B[mid]<x) l=mid;
else r=mid;
}
if(A[i]+B[r]==x)
{
cout<<i<<" "<<r;
break;
}
}
return 0;
}
终于懂了