16.数组元素的目标和

暴力做法

优化：

两个数组都是单调上升的

测试一个样例

3 6 9 13 15

1 4 7 10 14

目标值是22

应该输出 4 2

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 100010;
 4 int a[N], b[N];
 5 int main() {
 6     int n, m, x;
 7     cin >> n >> m >> x;
 8     for (int i = 0; i < n; i++) {
 9         cin >> a[i];
10     }
11     for (int i = 0; i < m; i++) {
12         cin >> b[i];
13     }
14     for (int i = 0, j = m - 1; i < n; i++) {
15         while (j >= 0 && a[i] + b[j] > x) {
16             j--;
17         }
18         if (a[i] + b[j] == x) {
19             cout << i << " " << j << endl;
20             return 0;
21         }
22     }
23     return 0;
24 }