思路一
这是我自己想的假的双指针算法
虽然我不是很会算时间复杂度,
不过我感觉我应该是水过去的
(有没有大佬帮我算一下这个时间复杂度到底是多少)
对于a和b两个数组
首先,让a和b头顶上的指针i,j同时移动,
1.如果刚好a[i]+b[j]==x的话,就找到答案了
2.如果a[i]+b[j][HTML_REMOVED]x的话,我们就让j往前移动
1)如果j移到某一位a[i]+b[j]==x的话,就找到答案了
2)如果j移到某一位a[i]+b[j][HTML_REMOVED]x的话就接着移动
但是这样我们发现有可能某一位的时候i应该取答案但是应该取答案的j在i后面我们这样找不到答案
很简单我们交换i,j再跑一遍就行了
CODE
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,m,x,a[N],b[N];
int main(){
scanf("%d%d%d",&n,&m,&x);
for(register int i=0; i<n; i++) scanf("%d",&a[i]);
for(register int i=0; i<m; i++) scanf("%d",&b[i]);
for(register int i=0; i<n; i++) {
int j = i;
while(a[i]+b[j]>x) j--;
if(a[i]+b[j]==x) { printf("%d %d\n",i,j); return 0;}
if(a[i]+b[j]<x) continue;
}
for(register int j=0; j<n; j++) {
int i = j;
while(a[i]+b[j]>x) i--;
if(a[i]+b[j]==x) { printf("%d %d\n",i,j); return 0;}
if(a[i]+b[j]<x) continue;
}
return 0;
}
思路二
这是真的双指针算法
include[HTML_REMOVED]
using namespace std;
const int N = 1e5+5;
int n,m,x,a[N],b[N];
int main(){
scanf(“%d%d%d”,&n,&m,&x);
for(register int i=0; i<n; i) scanf(“%d”,&a[i]);
for(register int i=0; i<m; i) scanf(“%d”,&b[i]);
for(register int i=0,j=m-1; i<n; i++) {
while(a[i]+b[j]>x) j--;
if(a[i]+b[j]==x) { printf("%d %d\n",i,j); return 0;}
if(a[i]+b[j]<x) continue;
}
return 0;
}
//需要先找到一个具有单调性的性质
```