AcWing 800. 数组元素的目标和

原题链接：https://www.acwing.com/problem/content/802/

题目分析

数组是升序的，a[i]从小变大，b[j]从大变小。

a代表目前可能匹配的a中最小值，若与目前b之和仍然大于k则必然j--；

i 从 0开始 从前往后遍历；j 从 m - 1开始 从后向前遍历；

和纯暴力的O(n2) 算法的区别就在于：j 指针不会回退

c++代码

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e5 + 10;

int n, m, k;
int a[N], b[N];
#define read(x) scanf("%d",&x)

int main()
{
    read(n), read(m), read(k);
    for (int i = 0; i < n; i ++ ) read(a[i]);
    for (int i = 0; i < m; i ++ ) read(b[i]);

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