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

最容易想的一个方法，读入两个数组后依次遍历每个值。
当然因为这道题的的数据量为1e5,暴力的话肯定是会超时的

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n,m,x;
int a[maxn],b[maxn];
int main() {
    cin>>n>>m>>x;
    unordered_map<int,int> t;

    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;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i]+b[j]==x){
                cout<<i<<" "<<j;
            }
        }
    }
}

算法2

(双指针) $O(n)$

我们观察到两个数组都是有序的，因此我们可以设置两个指针，一个从a数组的0位置开始，一个从b数组的m-1开始
因为一个是数组中最小的位置，一个是另外一个数组的最大位置、
所以如果此时a[i]+b[j]>x 我们就将j后移，因为如果<=，i一会是要往后走的，由于a数组是递增的
那么相加的值只会越来越大，由于题目保证有解，我们可以保证j从m-1到0的过程中一定是能找到解的
此时j不用像暴力一样每次回退到0

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n,m,x;
int a[maxn],b[maxn];
int main() {
    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<<endl;
        }
    }
}

算法3

(哈希表)

我们边读入a数组，边构造一个哈希表，键为x-a[i]的值，值为其下标，方便我们一会寻找与其匹配的值

之后我们读入b数组，在读入的同时查找哈希表中是否有这个键，如果找到的话，那么牵手成功.
不然的话继续读取知道找到就好了

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n,m,x;
int a[maxn],b[maxn];
int main() {
    cin>>n>>m>>x;
    unordered_map<int,int> t;
    for(int i=0; i<n; i++){
        scanf("%d",&a[i]);
        t[x-a[i]] = i;
    }
    for(int i=0; i<m; i++){
        scanf("%d",&b[i]);
        if(t.count(b[i])!=0){
            cout<<t[b[i]]<<" "<<i;
        }
    }
}