题目描述

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。

数据保证有唯一解。

样例

4 5 6
1 2 4 7
3 4 6 8 9

1 1

算法1

(暴力枚举)

1. 暴搜的结果当然是TLE啦，不过感觉可以记录一下hh。顺便跟后面的双指针优化算法对比一下。

时间复杂度

$O(nm)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, m, q;
int a[N], b[N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++) scanf("%d", &b[i]);

    for(int l1 = 0, l2 = 0; l1 < n; l1 ++)
    {
        if(a[l1] + b[l2] > q) continue;
        while(a[l1] + b[l2] < q && l2 < m) l2 ++;

        if(a[l1] + b[l2] == q) printf("%d %d", l1, l2);
        else l2 = 0;
    }
    return 0;
}

算法2

(双指针)

1. 双指针算法的优化就是找单调性。通常是先暴搜，然后找单调性。
2. 采用暴搜的话，会出现l1 = 0的时候，b数组所有元素和其相加，结果都< q的情况，如果从r2开始枚举，这种情况从一开始就可以避免，如果出现，那么r2前面的元素也一定不会超过q，所以直接换到a数组的下一个元素即可。
3. 如果r2对应的元素> q，说明那么答案可能在r2前面，这种单调性的掌握是需要学习的。
4. 暴搜的话会出现很多不必要情况的处理。而且双指针算法一般都不是从头开始枚举的，这跟暴搜没什么区别，所以下次做题找找头尾，找找单调性，从右往左看，都是可以的。

时间复杂度

$O(n+m)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, m, q;
int a[N], b[N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);

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

        if(a[i] + b[j] == q) printf("%d %d", i, j);
    }

    return 0;
}