You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2.2 KiB
2.2 KiB
一、题目描述
给定两个升序排序的有序数组 A
和 B
,以及一个目标值 x
。
数组下标从 0
开始。
请你求出满足 A[i]+B[j]=x
的数对 (i,j)
。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x
,分别表示 A
的长度,B
的长度以及目标值 x
。
第二行包含 n
个整数,表示数组 A
。
第三行包含 m
个整数,表示数组 B
。
输出格式
共一行,包含两个整数 ¥i
和 j
。
数据范围
数组长度不超过 10^5
。
同一数组内元素各不相同。
1
≤数组元素≤10^9
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1
二、思路总结
如果按传统思路,两个数组都从左到右遍历,时间复杂度妥妥的O(M*N)
,性能太差!
-
发现如果
A[i]+B[j]
要是大于目标值x
后,继续向前长大i,j
都是无意义的,可以优化。 -
如果固定
i
,遍历j
,再加上步骤(1)的优化,是不是就可以了呢? -
其实也缺失了一些东西:比如
a[1]+b[1]<x
,a[1]+b[2]<x
,a[1]+b[3]<x
,这样一把长大一个,长的太慢了,性能也不高。 -
如果能一次走两个,是不是会快?那怎么能一次走两个呢?可以考虑一个从左侧出发,另一个从右侧出发。双指针,两边出发。
总结
-
双指针
-
有序升序数组
-
对向而行,和大了就
j--
,和小了就i++
三、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main() {
int n, m, x;
cin >> n >> m >> x;
//读入a,b两个数组,注意它们两个都是升序的
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 (a[i] + b[j] == x) cout << i << " " << j << endl;
}
return 0;
}