i从头开始遍历a数组,j从后向前遍历s数组,由于两个数组都是单调递增的,所以当a[i]+s[j]>x时,需要将j往前移动直至a[i]+s[j]<=x。这时判断此刻的i和j是否是我们的答案,如果不是则将i往后移动一位,因为a[i+1]>=a[i],所以a[i+1]+s[j+1,j+2,..,m+1]>x,所以j无需后移。这样使时间复杂度变为O(n+m).
C++ 代码
#include<iostream>
using namespace std;
const int N=100010;
int a[N],s[N];
int main()
{
int n,m,x;
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",&s[i]);
}
for(int i=0,j=m-1;i<n;i++)
{
while(j>-1&&a[i]+s[j]>x) j--;
if(j>-1&&a[i]+s[j]==x) printf("%d %d",i,j);
}
return 0;
}