AcWing 800. 哈希和双指针两种方法
原题链接
简单
作者:
夏栀
,
2021-02-10 23:33:41
,
所有人可见
,
阅读 307
【2021.2.10】两种方法
#include <iostream>
#include <map>
using namespace std;
const int N = 1e5 + 5;
int A[N], B[N];
int n, m, x;
int res1 = 0, res2 = 0;
// 方法一:哈希表(该方法不需要考虑序列是否是升序的)
void fun1() {
map<int, int> mA;
for(int i = 0; i < n; i ++) mA[A[i]] = i; // 为数组A构建哈希表
for(int j = 0; j < m; j ++) { // 利用差值查询是否存在A中
if(mA.find(x - B[j]) != mA.end()){
res1 = mA[x - B[j]];
res2 = j;
break;
}
}
}
// 方法二:双指针(充分利用升序的条件)
void fun2() {
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) {
res1 = i;
res2 = j;
}
}
}
int main() {
scanf("%d%d%d", &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]);
fun2();
printf("%d %d", res1, res2);
return 0;
}