题目描述

给定两个升序排序的有序数组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

(双指针) $O(n)$

设置两个指针i,j，i为数组A的指针,j为B的指针
i从0开始，到n-1结束
j从m-1开始，到0结束。
每次判断A[i]+B[j] > x：
1、如果成立，代表B[j]过大，将j=j-1，
2、如果不成立，则有两种情况：
1）A[i]+B[j]==x，结束；
2）A[i]+B[j] < x，这时代表当前A[i]找不到合适的值，令i=i+1;
而j不用重新开始，因为A[i]+B[j] > x，而i变大了，这个条件仍然成立。

时间复杂度

参考文献

C++ 代码

#include<iostream>

using namespace std;

const int N=1e5+10;
int A[N],B[N];


int main(){
    int n,m,x;
    cin>>n>>m>>x;

    for(int i=0;i<n;i++)    scanf("%d",&A[i]);
    for(int i=0;i<m;i++)    scanf("%d",&B[i]);



    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) {
            cout<<i<<" "<<j;
            break;
        }
    }
}