【ACWing】800. 数组元素的目标和

题目地址：

https://www.acwing.com/problem/content/802/

给定两个升序数组 A A A和 B B B，再给定一个目标值 x x x，数组下标从 0 0 0开始，求满足 A [ i ] + B [ j ] = x A[i]+B[j]=x A[i]+B[j]=x的数对 ( i , j ) (i,j) (i,j)。题目保证只有唯一解。

输入格式：

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

输出格式：

共一行，包含两个整数 i i i和 j j j。

数据范围：

1 ≤ l A , l B ≤ 100000 1\le l_A,l_B\le 100000 1≤lA​,lB​≤100000

1 ≤ A [ i ] , B [ j ] ≤ 1 0 9 1\le A[i],B[j]\le 10^9 1≤A[i],B[j]≤109

思路是双指针。一个指针 i i i从 A [ 0 ] A[0] A[0]开始向右遍历，另一个指针 j j j从 B [ l B − 1 ] B[l_B-1] B[lB​−1]开始向左遍历。循环开始的时候check一下 A [ i ] + B [ j ] A[i]+B[j] A[i]+B[j]与 x x x的大小关系，如果相等，那就找到答案了，直接输出；如果 A [ i ] + B [ j ] > x A[i]+B[j]>x A[i]+B[j]>x，那么左移 j j j，否则右移 i i i。注意到，在循环的过程中， i i i和 j j j都不用回退，有单调性。代码如下：

#include <iostream>
using namespace std;

const int N = 100010;
int n, m, x;
int a[N], b[N];

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]);

    int i = 0, j = m - 1;
    while (a[i] + b[j] != x) {
        int s = a[i] + b[j];
        if (s > x) j--;
        else i++;
    }

    cout << i << ' ' << j << endl;

    return 0;
}
           

时间复杂度 O ( l A + l B ) O(l_A+l_B) O(lA​+lB​)，空间 O ( 1 ) O(1) O(1)。