题目描述
给定两个升序排序的有序数组 $A$ 和 $B$,以及一个目标值 $x$。
数组下标从 $0$ 开始。
请你求出满足 $A[i]+B[j]=x$ 的数对 $(i,j)$。
数据保证有唯一解。
输入格式
第一行包含三个整数 $n,m,x$,分别表示 $ A$ 的长度,$B$ 的长度以及目标值 $x$。
第二行包含 $n $ 个整数,表示数组 $A$。
第三行包含 $m$ 个整数,表示数组 $B$。
输出格式
共一行,包含两个整数 $i$ 和 $j$。
数据范围
数组长度不超过 $10^5$。
同一数组内元素各不相同。
$1≤数组元素≤10^9$
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1
算法1
(暴力枚举) $O(nm)$
本题直接想到的必然是暴力枚举,那也没啥说的了,上代码吧!
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int a[N],b[N];
int main()
{
int i,j,n,m,x;
cin>>n>>m>>x;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=m;i++)cin>>b[i];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i]+b[j]==x){
cout<<i-1<<' '<<j-1;
return 0;
}
}
但很不幸,这个代码完美的TLE了,而且只通过了10个数据
算法2
(双指针) $O(n+m)$
因为这里已经让数组升序排列了,所以我们可以从后面遍历。
还有一些优化如下:
a[i]+b[j]若>x,则a[i+1]+b[j]也>x,所以我们只要初始化一遍j
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],b[N];
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);//不加上面这三行是528ms,加了是128ms
int i,j,n,m,x;
cin>>n>>m>>x;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=m;i++)cin>>b[i];
j=m;
for(i=1;i<=n;i++){
while(j>0&&b[j]+a[i]>x)j--;
if(j>0&&b[j]+a[i]==x){cout<<i-1<<' '<<j-1;return 0;}
}
}
于是,成功AC
算法3
(二分) $O(nlogm)$
此题用二分也可以,只不过写的时候要注意几个细节问题,代码里会标注出来
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],b[N],n,m,x;
int sol(int k)
{
int l=1,r=m;
while(l<=r){
int mid=(l+r)/2;
if(b[mid]>k)r=mid-1;
else if(b[mid]<k)l=mid+1;
else return mid;
}
return -1;//细节1,针对查找不到
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int i,j;
cin>>n>>m>>x;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=m;i++)cin>>b[i];
for(i=1;i<=n;i++){
int k=sol(x-a[i]);
if(k!=-1&&b[k]+a[i]==x){cout<<i-1<<' '<<k-1;break;}//细节2,针对查找不到时的返回-1做的if判断
}
}