acwing 800. 数组元素的目标和

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x 的数对 (i,j)。

数据保证有唯一解。

输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。

第二行包含 n 个整数，表示数组 A。

第三行包含 m 个整数，表示数组 B。

输出格式
共一行，包含两个整数 i 和 j。

数据范围
数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1

方法1： 直接想到暴力求解 O(n²)

for(int i =0; i < n; i++)
	for(int j = 0; j < m; j ++)
		if(a[i] + b[j] == x) cout << xxx;

利用双指针进行优化： O(n) 利用了单调性

图解：

思考： 这里为什么是O（n）

for(int i =0; i < n; i++)
	while(j >=0 && a[i] + b[j] > x)  j --;

这里j 只是回退了，它在指针i移动时，并不会回到最后重新开始。

思想：
为了减少循环，采用了两个指针来保证能遍历符合要求的所有数；
i指针从A数组的头开始，此时a[i]最小；
j指针从B数组的尾开始，此时b[j]最大；

在i = 0 时，判断a[i] + b[j] 的值，如果大于x，j- -；
也就是说b[j]的值一直在减小；

那么当a[i] + b[j] 的值第一次小于x时，j指针的左边的数与a[i]相加一定都小于x了；那么我们只能增大a[i]的值；
于是i ++;

自此开始反复循环,如果a[i] + b[j] 大于x，就减小b[j]（相当于将j指针左移）反之，就增大a[i]（相当于i指针右移）
这样，一定保证了每一个符合要求的两个数都能加一遍，判断是不是和等于x。

code:

#include <iostream>

using namespace std;
const int N = 100010;

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

int main()
{
    
    cin >> n >> m >> k;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < m; i ++) cin >> b[i];
    
    for(int i = 0, j  = m -1; i < n; i ++)
    {
    
      while(j >=0 && a[i] + b[j] > k ) j --;
      if(k == a[i] + b[j])
      {
    
          cout << i << ' ' << j << endl;
      }
    }
    return 0;    
}