题目描述
给定两个升序排序的有序数组A和B,以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。
数据保证有唯一解。
算法1
unordered_map
C++ 代码
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 100010;
int n,m,x;
int B[N];
int main(){
cin >> n >> m >> x;
unordered_map<int,int> map;
int a;
for(int i = 0;i < n;i ++) cin >> a,map[a] = i;
for(int i = 0;i < m;i ++) cin >> B[i];
for(int i = 0;i < m;i ++){
while(map.count(x-B[i])){
cout << map[x - B[i]] << ' ' << i << endl;
break;
}
}
return 0;
}
算法2
双指针(双数组对撞指针)
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
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];
int i = 0,j = m - 1;// 初始时i指向A数组最小的元素,j指向B数组最大的元素
while(i < n && j >= 0){
if(A[i] + B[j] > x) j--;// 大于x说明应将j指针左移使整体变小
else if(A[i] + B[j] < x) i++;// 反之i指针右移使整体变大
else {
cout << i << ' ' << j << endl;
break;
}
}
return 0;
}