算法1

(暴力枚举) $O(n*m)$

暴力会超时

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];
int n, m, x;

int main(){
    scanf("%d%d%d", &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; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i] + b[j] == x){
                cout << i << ' ' << j << endl;
                return 0;
            }
        }
    }

    return 0;
}

算法2

i从左往右找, j 从往左找

时间复杂度

O(n)

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];
int n, m, x;

int main(){
    scanf("%d%d%d", &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 && b[j] + a[i] > x) j--;
        if(a[i] + b[j] == x){
            cout << i << ' ' << j << endl;
            return 0;
        }
    }

    return 0;
}