原题链接：https://www.acwing.com/problem/content/submission/code_detail/22373905/

两种思路：

  • ，因此可以采用二分查找的思路，时间复杂度。
  • 由于所给数组已经有序，可以采用矩阵搜索的思路。等价于在一个矩阵中寻找目标值，其中满足沿轴方向和轴方向都是递增的。这种方法时间复杂度为。
#include <iostream>
#include <algorithm>

int n, m, x;  

int bin_search(int b[], int left, int right, int target) {
    int i = left, j = right, mid;
    while (i < j) {
        mid = (i + j) >> 1;
        if (b[mid] > target) j = mid;
        else if (b[mid] < target) i = mid + 1;
        else return mid;
    }
    return -1;
}

void matrix_search(int a[], int b[], int target) {
    int i = 0, j = m-1;
    while (m >= 0 && i < n) {
        if (a[i] + b[j] > target) j--;
        else if (a[i] + b[j] < target) i++;
        else {
            printf("%d %d\n", i, j);
            return;
        }
    }
    printf("-1 -1\n");
}


int main() {
    scanf("%d %d %d", &n, &m, &x);
    int a[n], b[m];
    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) {
    //     int j = bin_search(b, 0, m, x - a[i]);
    //     if (j != -1) {
    //         printf("%d %d", i, j);
    //         break;
    //     }
    // }
    
    matrix_search(a, b, x);
    
    return 0;
}