哈希表/哈希查找

记录一下自己不会做的题。

优质数对

问题描述

给你一个长度为N的数组A和B，对于满足以下三个条件的数对(i,j)被称之为优质数对：

请你输出有多少个优质数对？

输入格式

第一行输入一个整数N，表示A和B的长度。

第二行输入N个整数，表示数组A。

第二行输入N个整数，表示数组B。

数据范围保证：，

输出格式

输出一个整数，表示优质数对的数目。

思路

通过超级基数SB把条件二和条件三合并。变成条件：，实现i和j的分离。将两次遍历化简，使得只需要一次遍历，完成查找前面的值和插入数据。
使用哈希表建立1.中条件的结果值，并建立cnt数组与哈希表对齐，储存的前面结果值出现的次数。通过哈希表化简查找过程，进行结果值的对比并进行累加。

实现过程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SB 1000000003
#define maxn 100003
#define max2n (2 * maxn)
int A[maxn], B[maxn];
long long ht[max2n];
int cnt[max2n];

void hashInsert(long long num){
  int offset = num % max2n;
  while(1){
    if(ht[offset] == -1){
      ht[offset] = num;
      cnt[offset] = 1;
      return;
    }
    else if(ht[offset] == num){
      cnt[offset] += 1;
      return;
    }
    else{
      offset = offset + 1;
      if(offset >= max2n){
        offset = 0;
      }
    }
  }
  return;
}

int hashGet(long long num){
  int offset = num % max2n;
  while(1){
    if(ht[offset] == -1){
      return 0;
    }
    else if(ht[offset] == num){
      return cnt[offset];
    }
    else{
      offset = offset + 1;
      if(offset >= max2n){
        offset = 0;
      }
    }
  }
  return 0;
}
int main(int argc, char *argv[])
{
  int N;
  scanf("%d", &N);
  for(int i = 0; i < N; ++i){
    scanf("%d", &A[i]);
  }
  for(int i = 0; i < N; ++i){
    scanf("%d", &B[i]);
  }
  memset(ht, -1, sizeof(ht));
  memset(cnt, 0, sizeof(cnt));
  long long num = 0;
  long long count = 0;
  for(int i = 0; i < N; ++i){
    num = ((long long) B[i]) * SB + A[i];
    count += hashGet(num);
    num = ((long long) A[i]) * SB + B[i];
    hashInsert(num);
  }
  printf("%lld", count);
  return 0;
}