哈希表

unordered_map<int, int> hashtable;

关键功能在于能够快速查找

两数之和

题意：在数组中找出两个数的和等于给定的一定目标值

这题暴力可以，数据很小，主要想学习一下哈希表的做法。

哈希表做法：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};
//将查找这一步由O（n）降低到了O(1),利用哈希表可以快速查找的特点。

字符串哈希

题意：给一个字符串，给两个区间问两个区间内的字符串是否相等；

思路：字符串哈希，哈希值一样则相等。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
#define sc(n) scanf("%d",&n)
#define print(n) printf("%d\n",n)
#define endl "\n";
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int N=1000010,P=131;
const int MOD = 1e9 + 7;
const int INF=1e9;
const double eps=1e-5;

int n,m;
int a[N],b[N];
ull h[N],p[N];

ull get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
char s[N*2];
int main(){
    cin>>n>>m;

    cin>>s+1;
    //s=" "+s;
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*P+s[i];
        p[i]=p[i-1]*P;
    }

    while(m--){
        int l1,l2,r1,r2;
        cin>>l1>>r1>>l2>>r2;
        //cout<<get(l1,r1)<<" "<<get(l1,r2)<<endl;
        if(get(l1,r1)==get(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}
/*
5
55 30 5 4 2
100 20 10 10 5
*/