双指针,哈希,二分解法
问题
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
双指针(500ms)
先写纯暴力法,分析这里满足单调性,所以可以双指针O(m+n)
#include<iostream>
#include<algorithm>
using namespace std;
const int N= 1e5+10;
int m,n,x;
int a[N],b[N];
int main()
{
cin>>n>>m>>x;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
int i,j=m-1;
for(i=0;i<n;i++)
{
while(j>=0&&a[i]+b[j]>x)
{
j--;
}
if(a[i]+b[j]==x)
{
break;
}
}
cout<<i<<" "<<j<<endl;
return 0;
}
二分(571ms)
对找x-a[i]进行简单的二分O(nlogn)
#include<iostream>
#include<algorithm>
using namespace std;
const int N= 1e5+10;
int m,n,x;
int a[N],b[N];
int main()
{
cin>>n>>m>>x;
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 find=x-a[i];
int l=0,r=m-1;
while(l<r)
{
int mid=l+r+1>>1;
if(b[mid]<=find)
{
l=mid;
}
else
{
r=mid-1;
}
}
if(b[r]==find)
{
cout<<i<<" "<<r<<endl;
}
}
return 0;
}
哈希(918ms)
这里哈希本来应该是理论最快的(内层循环达到O(1)),
但是调用stl的话,在建立哈希等时候会消耗时间。
不调用stl,直接数组开1e9会爆掉。
所以时间反而最长了???
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N= 1e5+10;
int m,n,x;
int a[N],b[N];
unordered_map <int,int> h;
int main()
{
cin>>n>>m>>x;
for(int i=0;i<n;i++)
{
cin>>a[i];
h[a[i]]=i;
}
for(int i=0;i<m;i++)
{
cin>>b[i];
if(h.count(x-b[i]))
{
cout<<h[x-b[i]]<<" "<<i<<endl;
}
}
return 0;
}