题目

给定两个升序排序的有序数组 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

来源：acwing算法基础 800. 数组元素的目标和

---

思路（注意事项）

双指针，一个从前面遍历，一个从后面遍历。相较于暴力解O(n^2)，区别是后面的指针不会倒退。

---

纯代码

#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 1;
int a[N], b[N];int main()
{int n, m, x;cin >> n >> m >> x;for (int i = 0; i < n; i ++) scanf ("%d", &a[i]);for (int i = 0; i < m; i ++) scanf ("%d", &b[i]);int i = 0, j = m - 1;while (a[i] + b[j] != x)if (a[i] + b[j] > x) j --;else i ++;cout << i << " " << j << endl;return 0; 
}

题解（带注释）

#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 1; // 定义数组最大长度
int a[N], b[N];        // a和b分别存储两个输入数组int main() {int n, m, x;       // n-数组a的长度，m-数组b的长度，x-目标和cin >> n >> m >> x; // 输入n, m, x// 输入数组afor (int i = 0; i < n; i++) scanf("%d", &a[i]);// 输入数组bfor (int i = 0; i < m; i++) scanf("%d", &b[i]);// 双指针算法：i从a的起始位置开始，j从b的末尾开始int i = 0, j = m - 1;while (a[i] + b[j] != x) { // 当a[i] + b[j]不等于x时循环if (a[i] + b[j] > x) j--; // 如果和大于x，移动j向左（减小和）else i++;                 // 如果和小于x，移动i向右（增大和）}// 输出满足条件的下标i和jcout << i << " " << j << endl;return 0;
}