【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)。