双指针算法思路
题目给定这是两个升序数组,很明显如果用报错的那种方法时间复杂度会高,那么如果不将两个指针都放在数组开头,一个放在数组头,一个放在数组尾,那么我们从第一个数组头开始遍历,在内部从第二个数组尾开始遍历,当A[i]+B[j]>x的时候就要把j–,直到A[i]+B[j]==x,但是如果小于x,我们也不需要担心,只要在外部i++,这样A[i]就会变大,直到A[i]+B[j]==x或者>x,当>x,就继续执行上述过程,=x就可以直接输出了。
时间复杂度是O(n+m)
超时
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,x;
int A[N],B[N];
int main()
{
scanf("%d%d%d",&n,&m,&x);
for(int i=0;i<n;i++) scanf("%d", &A[i]);
for(int i=0;i<m;i++) scanf("%d", &B[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(A[i]+B[j]==x)
{
printf("%d %d",i,j);
}
}
}
return 0;
}
双指针算法
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,x;
int A[N],B[N];
int main()
{
scanf("%d%d%d",&n,&m,&x);
for(int i=0;i<n;i++) scanf("%d", &A[i]);
for(int i=0;i<m;i++) scanf("%d", &B[i]);
pair<int,int> ans;
for(int i=0,j=m-1;i<n;i++)
{
while(A[i]+B[j]>x) j--;
if(A[i]+B[j]==x)
{
ans={i,j};
break;
}
}
printf("%d %d",ans.first,ans.second);
return 0;
}
二分
既然要找两个和为x的数,那么我们可以把它转换成确定了一个y为A[i]后,在 B中找出x−y 的问题。显然我们可以二分查找,算法复杂度为 O(nlogn)。
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,x;
int A[N],B[N];
int main()
{
scanf("%d%d%d",&n,&m,&x);
for(int i=0;i<n;i++) scanf("%d", &A[i]);
for(int i=0;i<m;i++) scanf("%d", &B[i]);
for(int i=0;i<n;i++)
{
int b=x-A[i];
int l=0,r=m-1;
while(l<=r)
{
int mid=l+r>>1;
if(B[mid]>b) r=mid-1;
else if(B[mid]<b) l=mid+1;
else
{
printf("%d %d",i,mid);
break;
}
}
}
return 0;
}
哈希
既然有了二分查找x-A[i],那么我们也可以想到哈希
我们把输入A[i]时每个数存在哈希表里面,对于每个输入的B[i]看x-B[i]是否出现在哈希表中即可
#include<iostream>
#include<unordered_map>
using namespace std;
const int N=1e5+10;
int n,m,x;
int A[N],B[N];
unordered_map<int,int> map;
int main()
{
scanf("%d%d%d",&n,&m,&x);
for(int i=0;i<n;i++)
{
scanf("%d", &A[i]);
map[A[i]]=i;
}
for(int i=0;i<m;i++)
{
scanf("%d",&B[i]);
if(map.count(x-B[i]))
{
printf("%d %d",map[x-B[i]],i);
}
}
return 0;
}