acwing 800. Target and of array elements

Given two ordered arrays sorted in ascending order A and B, And a target value x.

Array index from 0 Start .

Please find satisfaction A[i]+B[j]=x The number of (i,j).

Data guarantees a unique solution .

Input format
The first line contains three integers n,m,x, respectively A The length of ,B The length and target value of x.

The second line contains n It's an integer , Represents an array A.

The third line contains m It's an integer , Represents an array B.

Output format
All in one line , Contains two integers i and j.

Data range
Array length not more than 105.
The elements in the same array are different .
1≤ Array elements ≤109
sample input ：
4 5 6
1 2 4 7
3 4 6 8 9
sample output ：
1 1

Method 1： Think of violence directly O(n²)

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

Optimize with double pointers ： O(n) Using monotonicity

The illustration ：

reflection ： Why is this O（n）

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

here j Just back off , It's in the pointer i When moving , It won't go back to the end and start again .

thought ：
To reduce circulation , Two pointers are used to ensure that all numbers that meet the requirements can be traversed ;
i Pointer from A Start with the header of the array , here a[i] Minimum ;
j Pointer from B Start at the end of the array , here b[j] Maximum ;

stay i = 0 when , Judge a[i] + b[j] Value , If it is greater than x,j- -;
in other words b[j] The value of has been decreasing ;

So when a[i] + b[j] The value of is less than... For the first time x when ,j The number to the left of the pointer is the same as a[i] The sum must be less than x 了 ; Then we can only increase a[i] Value ;
therefore i ++;

Since then, it has been repeated , If a[i] + b[j] Greater than x, Just reduce b[j]（ Is equivalent to j Move the pointer to the left ） conversely , Just increase a[i]（ amount to i Move the pointer to the right. ）
such , It must be ensured that every two numbers that meet the requirements can be added again , Judge whether sum equals 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;    
}