本文是基本常见的哈希表题解

一、哈希表简介

一般哈希表都是用来快速判断一个元素是否出现集合里

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。

接下来哈希碰撞登场

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

常见的三种哈希结构

数组

set

map

大体的判断方式:

数组:使用场景哈希值比较小,范围可控,例如26个字母类似的(如果是1, 5, 100万这样分散的不适合数组)

set:如果数值很大的话,就用set

map:如果key对应value的话,我们就用map

总结:

总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

二、哈希表题解

242. 有效的字母异位词

自己的写法,也就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isAnagram(string s, string t) {
        // 数组下标是a到z
        int array[26] = {0}; // 初始时,出现次数都是0
        for (char c : s) {
            array[(int)(c - 'a')]++;
        }
        for (char c : t) {
            array[(int)(c - 'a')]--;
        }

        for (int i = 0; i < 26; i++) {
            if (array[i] != 0) {
                return false;
            }
        }
        return true;
    }
};

349. 两个数组的交集

我的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        unordered_set<int> u_set2(nums2.begin(), nums2.end());
        unordered_set<int> u_set1(nums1.begin(), nums1.end());
        vector<int> ret;
        for (const int &ele : u_set1) {
            if (u_set2.find(ele) != u_set2.end()) {
                ret.push_back(ele);
            }
        }
        return ret;
    }
};

改进后的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        unordered_set<int> u_set1(nums1.begin(), nums1.end());
        unordered_set<int> ret;
        for (int &ele : nums2) {
            if (u_set1.find(ele) != u_set1.end()) {
                ret.insert(ele);
            }
        }
        return vector<int>(ret.begin(), ret.end());
    }
};

后来leetcode又增加了描述

  • 0 <= nums1[i], nums2[i] <= 1000

所以就可以 使用数组来做哈希表了， 因为数组设置下标都是 1000以内的。

数组的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        int a[1010] = {0};
        for (int ele : nums1) {
            a[ele] = 1;
        }

        vector<int> ret;
        for (int ele : nums2) {
            if (a[ele] == 1) {
                ret.push_back(ele);
                a[ele] = 0; // 相当于去重操作
            }
        }
        return ret;
    }
};

或者这样写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        int a[1010] = {0};
        for (int ele : nums1) {
            a[ele] = 1;
        }

        unordered_set<int> ret;
        for (int ele : nums2) {
            if (a[ele] == 1) {
                ret.insert(ele);
            }
        }
        return vector<int>(ret.begin(), ret.end());
    }
};

待更新……