AcWing 800. 哈希和双指针两种方法

哈希值,又称:散列函式(或散列算法,又称哈希函式,英语:Hash Function)是一种从任何一种数据中创建小的数字“指纹”的方法。想要了解哈希值,就需要了解哈希函数的性质。

来源：哈希交流群浏览次更新时间：2022-05-15 20:07

【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;

}