题目描述

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。

数据保证有唯一解。

输入格式
第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。

第二行包含n个整数，表示数组A。

第三行包含m个整数，表示数组B。

输出格式
共一行，包含两个整数 i 和 j。

数据范围
数组长度不超过100000。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：

4 5 6
1 2 4 7
3 4 6 8 9

输出样例：

1 1

算法1（双指针）

思路

1.准备i,j两个指针,i指向a数组开头，j指向b数组尾

2.要找到a[i]+b[j]>=x最接近的下标,因为a,b都升序，i往后走,j一定往前走

时间复杂度

$O(n)$

Java 代码

import java.util.*;

public class Main {
    private static int N = 100010;
    private static int[] a = new int[N];
    private static int[] b = new int[N];
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int x = scanner.nextInt();
        for(int i = 0;i < n;i++){
            a[i] = scanner.nextInt();
        }
        for(int i = 0;i < m;i++){
            b[i] = scanner.nextInt();
        }
        for(int i = 0,j = m - 1;i < n;i++){
            while(j > 0 && a[i] + b[j] > x){
                j--;
            }
            if(a[i] + b[j] == x){
                System.out.println(i+" "+j);
                break;
            }
        }

    }
}