题目描述
有两个单调递增的数组a,b,
a:1 2 4 7
b:3 4 6 8 9
输出满足a[i] + b[j] = x的索引i,j
题目保证只有一个解
算法思路
1:声明两个指针i,j,i指针指向a数组的第一个数,也就是1,j指针指向b数组的最后一个数,也就是9,
2:如果a[i] + b[j] > x的话,说明这个数太大,我们就要想办法让a[i] + b[j]变小,因为两个数组都是单调递增的,所以只能让j指针向左走,才能变小;
3:直到a[i] + b[j] < x,这样说明数太小了,我们就要想办法把数变大,也就是让i指针向右走;
4:直到a[i] + b[j] = x,因为题目有唯一解,所以找到结果就可以break了
java代码
import java.util.Scanner;
public class Main{
private static int N = 100010;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int x = in.nextInt();
int[] a = new int[N];
int[] b = new int[N];
for(int i = 0; i < n; i ++) a[i] = in.nextInt();
for(int i = 0; i < m; i ++) b[i] = in.nextInt();
for(int i = 0 , j = m - 1; i < n; i++ ){
while(j >= 0 && a[i] + b[j] > x) j--; //j指针先走,当<x的话就停止,i向左走一步,j继续向前走;知道等于x输出答案
if(a[i] + b[j] == x){
System.out.print(i + " " + j); //因为保证有唯一解,所以找到一个就可以break了
break;
}
}
}
}