Acwing基础课第800题-简单-数组元素的目标和

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

数组下标从 0 开始。

请你求出满足 �[�]+�[�]=�的数对 (�,�)。

数据保证有唯一解。

输入格式

第一行包含三个整数 �,�,�，分别表示 � 的长度，� 的长度以及目标值 �。

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

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

输出格式

共一行，包含两个整数 � 和 �。

数据范围

数组长度不超过。数组长度不超过。数组长度不超过105。
同一数组内元素各不相同。同一数组内元素各不相同。同一数组内元素各不相同。
数组元素数组元素1≤数组元素≤109

输入样例

4 5 6 1 2 4 7 3 4 6 8 9

输出样例

1 1

思路解析：

算法：双指针

代码：

#include <iostream> using namespace std; const int N = 1e5 + 10; int n, m, x; int a[N], b[N]; int main() { cin >> n >> m >> x; 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] > x) j -- ; if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl; } return 0; }