# 题目大意

给定两个升序的有序数组 A,BA,B,长度分别为 n,mn,m,以及一个目标值 xx
请你求出满足 Ai+Bj=xA_i+B_j=x 的所有数对 (i,j)(i,j)

# 数据范围

  • 1n,m1e51 \le n, m \le 1e5

# 题解

两个数组都是升序的,显然,如果 aia_i 可以和 bjb_j 组合成 xx 的话,那么 AA 数组 ii 后面的所有,都至少只能和 BB 数组 jj 前面的结合成 xx
所以一个从 i = 1 开始,一个从 j = m 开始,双指针扫一下

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve () {
cin >> n >> m >> x;
vector<int> a(n + 1), b(m + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];

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

if (j >= 1 && a[i] + b[j] == x)
cout << i - 1 << " " << j - 1 << endl;
}
}