数组元素的目标和

思路分析

双指针问题，首先还是想出一个基础的暴力做法，再想着如何优化

1. 暴力做法

先枚举第一个数组的数，其次从前向后（或是从后向前）依次遍历，如果找到则结束
这个时间复杂度很明显是$O(n ^ 2)$的

2. 双指针

我们可以发现，由于两个数组是单调递增的，当第二个数组数从后往前走的时候，是不会后退的

因为若$a[i] + b[j] > x$, 可推出$a[i + 1] + b[j] > x$，即第一个数向后走的时候，第二个数只能往前走

这是一个单调性，那么我们就可以利用它，$i$指向第一个数组的当前数字，$j$指向第二个数组
当$a[i] + b[j] > x$, $j$往后，停下时候，$a[i] + b[j] <=x$，看看此时是否相等，相等则输出解；不相等，$i$就向后移动

本题目保证了数据有唯一解，若是可以有多组解，那么复杂度必然是$O(n ^ 2)$的

时间复杂度分析

虽然有两层循环，但是$j$最多只会走$n$次, $i$也是$n$次
时间复杂度是$O(n)$的

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

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

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 && a[i] + b[j] > x) j -- ;//找到第一个满足，a[i] + b[j] <= x的点
        if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;//若相等则输出，否则i右移
    }

    return 0;
}