【代码随想录】哈希表

发表于 更新于 分类于 阅读次数： 23 本文字数： 5.8k 阅读时长 ≈ 19 分钟

哈希表理论基础

哈希表就是利用一个 hash 函数，将元素的值 value 映射到一个索引范围内。比如通过取模运算将任意整数 X 映射到 [0, TableSize - 1]，那么 TableSize 是哈希表的大小，索引范围就是 [0, TableSize - 1]。

根据元素的值就能实现常数级的查找。

主要用于需要判断一个元素是否存在一个集合中。

哈希函数的问题是：如果元素的取值空间远大于索引的取值空间，那么有可能会导致不同的元素被映射到相同的位置，也就是发生了碰撞。对于碰撞的处理有以下几种处理方式：线性探测、二次探测、开链等。

常用的哈希结构：

  • 数组
  • set （集合）
  • map (映射)

在 C++ 的 STL 中提供基于不同底层数据结构的 set 和 map，详细内容可见个人博客：https://guomw.net/

对于 set 来说，底层实现和优劣对比如下：（此处省略了 unordered_multiset）

集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 否 否 O(log n) O(log n)
std::multiset 红黑树 有序 是 否 O(logn) O(logn)
std::unordered_set 哈希表 无序 否 否 O(1) O(1)

底层数据结构是红黑树的 set，由于红黑树是一种平衡二叉树，是根据 key 值进行排序，所以 key 值不能修改。只能删除和增加。

对于 map 来说，底层实现和优劣对比如下：

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key 有序 key 不可重复 key 不可修改 O(logn) O(logn)
std::multimap 红黑树 key 有序 key 可重复 key 不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key 无序 key 不可重复 key 不可修改 O(1) O(1)

综上，如果想要使用哈希表解决哈希问题，优先使用底层实现为 hash table 的 unordered_set 和 unordered_map。

哈希表是使用空间换取时间的数据结构，set 的元素是一个值，map 个每个元素是键值对。

有效的字母异位词

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

思路：使用一个哈希表记录 26 个小写字母在两个字符串中出现次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isAnagram(string s, string t) {
        // 创建一个hash表用于记录在S串中各个字母出现的次数
        int hash_table[26] = {0};
        // 遍历S串
        for (char c : s) hash_table[c - 'a']++;

        // 遍历T串
        for (char c : t) hash_table[c - 'a']--;

        // 遍历hash表
        for (int i = 0; i < 26; i++) {
            if (hash_table[i] != 0) return false;
        }

        return true;
    }
};

时间复杂度 O (N + M + 26)，遍历 S 串、T 串和 hash 表各一次；空间复杂度 O (1)

相关题目：

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

思路：使用一个 unordered_map 记录 magazine 中字符的数量，然后判断能否满足 ransomNote 的需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        // 创建一个hash表
        unordered_map<char, int> hash_table;

        // 统计第二个字符串中的字母数量
        for (char c : magazine) hash_table[c]++; // []方法会在没有这个元素时创建一个初始值为0的元素

        // 遍历第一个字符串查看是否满足
        for (char c : ransomNote) {
            // 如果没有该字母或者该字母已经没有可用次数则返回false
            if (hash_table.find(c) == hash_table.end() ||
                hash_table[c] == 0) return false;
            
            hash_table[c]--;
        }

        return true;
    }
};

时间复杂度 O (N + M)，遍历两个字符串的时间；空间复杂度 O (S)，S 指的是 magazine 中不同的字符个数。

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

思路：把排序之后的 string 作为键，把列表作为值。遍历每一个字符串，然后排序之后作为键值判断是否相等，在键值对应的列表中添加该字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash_table;
        for (string s : strs) {
            string temp = s; // 创建一个临时副本
            sort(temp.begin(), temp.end());

            hash_table[temp].push_back(s);
        }

        // 结果数组
        vector<vector<string>> result;
        for (auto it = hash_table.begin(); it != hash_table.end(); ++it) {
            result.push_back((*it).second);
        }

        return result;
    }
};

时间复杂度 O，遍历字符串列表的时间复杂度是 O (n)，对于每一个字符串进行排序的时间复杂度是 O (nlogn)，对于字符串进行 hash 函数的复杂度是 O (1)，插入的时间复杂度是 O (1)，因此遍历并加入 hash_table 的时间复杂度是 O (n^2logn)；空间复杂度 O (不同的字母异位词的个数)

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

思路：采用滑动窗口的方法：
1. 窗口中是什么：窗口中记录当前子串中有效字母（即在目标字符串中的字符）出现的次数

2. 什么时候移动右边界：循环每次向后移动一位

3. 什么时候移动左边界：当窗口中元素满足条件时，移动到不满足条件为止
满足条件即字串长度等于目标串的长度，不满足条件就是向后移动一位导致小于目标串长度。

在这里需要判断当前窗口中的字串是否为异位词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int>windows, need;
        for (char c : p) need[c]++; // 统计需要字符的个数
        int valid = 0; // 表示当前窗口中满足字符的个数
        int left, right;
        left = 0; // 窗口左边界
        right = 0; // 窗口右边界
        int s_len = s.length();
        int p_len = p.length();
        vector<int> result;

        while (right < s_len) {
            char c = s[right];
            right++; // 右边界移动

            // 如果当前字符在need中
            if (need.count(c)) {
                windows[c]++;
                if (windows[c] == need[c]) valid++;
            }

            // 判断子串长度是否等于目标串长度
            if (right - left == p_len) {
                if (valid == need.size()) result.push_back(left);

                // 移动左边界使得条件不满足
                char d = s[left];
                left++;
                if (need.count(d)) {
                    if (windows[d] == need[d]) valid--;
                    windows[d]--;
                }
            }
        }

        return result;
    }
};

时间复杂度 O (n-m+1)，左边界最多移动到这个位置；空间复杂度 O (需要的字符个数)

两个数组的交集

349. 两个数组的交集

先求第一个数组的集合，然后遍历第第二个数组，将其中在第一个集合中的元素放入到另一个集合中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 创建set用于装下唯一元素
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2; // 第二个列表中出现在第一个集合中的元素
        
        // 遍历第二个列表
        for (int x : nums2) {
            // 如果不在第一个集合中说明不是交集中的元素
            if (set1.find(x) == set1.end()) continue;
            
            set2.insert(x);
        }

        vector<int> result(set2.begin(), set2.end());
        return result;
    }
};

时间复杂度 O (n + m)，遍历第一个数组一次，遍历第二个数组一次，遍历交集集合一次；空间复杂度 O (n)

350. 两个数组的交集 II

思路：使用 map 记录第一个数组每个元素出现次数；然后遍历第二个数组，如果当前元素在第一个数组中出现过并且可用次数大于 0 则加入结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        // map用于记录每个元素出现的次数
        unordered_map<int, int> hash_table;
        for (int x : nums1) hash_table[x]++;

        vector<int> result;
        // 遍历第二个数组
        for (int x : nums2) {
            // 如果当前元素作为键值存在于hash表中并且使用次数大于0
            if (hash_table.count(x) && hash_table[x] > 0) {
                result.push_back(x);
                hash_table[x]--;
            }
        }

        return result;
    }
};

时间复杂度 O (n)，遍历两个数组的时间；空间复杂度 O (n)

进阶：如果给定的数组已经排好序呢？你将如何优化你的算法？

给好顺序的话就使用两个指针分别指向两个数组，如果两个指针指向元素相同，那么就将该元素加入结果并同时向后移动；如果不同，判断两个元素大小，元素小的那个指针向后移动，直到等于或者大于大的元素值，然后进入下一轮循环。

时间复杂度 O (min (n, m))，其中 n、m 分别是两个数组大小。

进阶：如果 nums1 的大小比 nums2 小，哪种方法更优？

第二种。

进阶：如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

上述算法可以解决这个情况，将第一个数组的元素每次出现的次数记录为使用次数，每次找到符合要求的元素就减少一次使用次数。这样就不同担心需要整体遍历完第二个数组才能进行判断。

快乐数

第 202 题。快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路：每次判断每个位置上的数字的平方和之后，如果结果是 1 就返回 true；否则判断是否出现过该元素，防止出现循环，所以使用 set 保存历史数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isHappy(int n) {
        // 创建一个hash表用于保存变化过程中已经出现的数字
        unordered_set<int> hash_table;

        int temp = n; // 保存中间变量
        while (hash_table.find(temp) == hash_table.end()) {
            hash_table.insert(temp);

            int sum = 0;
            while (temp != 0) {
                sum += pow(temp % 10, 2);
                temp /= 10;
            }

            temp = sum;
            if (temp == 1) return true;
        }

        return false;
    }
};

时间复杂度 O (logn)。详细参考题解

两数之和

第 1 题：两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

思路 1：暴力法：采用双层循环，外层循环遍历每一个元素，内存循环遍历后面的元素，判断两个元素相加是否为 target。

时间复杂度 O (n^2)；空间复杂度 O (1)

思路 2：采取空间换取时间的做法，在 map 中保存（target-nums1，nums1 对应的下标），nums1 表示遍历的每一个数字。遍历时，如果可以根据 target-nums1 找到键，说明找到一对合适的结果；否则，将（target-nums1，nums1）插入 map。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        
        // 遍历数组
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            int need_val = target - nums[i];
            if (map.find(need_val) != map.end()) 
                return vector<int>{map[need_val], i};
            
            // 否则将当前值作为键，将当前值对应下标作为值
            map[nums[i]] = i;
        }

        return vector<int>{-1, -1};
    }
};

时间复杂度 O (n)，遍历数组的时间；空间复杂度 O (n)

收获：

  • 为什么会想到用哈希表：当需要判断一个元素是否存在时
  • 哈希表为什么用 map：因为数组的下标只能是 int，set 没有下标，map 用于存一个映射。
  • 本题 map 是用来存什么的：key 存 target - nums1（第一个加数） value 存这个数对应的下标
  • map 中的 key 和 value 用来存什么的

四数相加

第 454 题：

给定四个包含整数的数组列表 A , B , C , D , 计算有多少个元组 (i, j, k, l) ，使得 A [i] + B [j] + C [k] + D [l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

思路 1：四层循环遍历四个数组，计算四个数字之和是否为 0.

时间复杂度 O (n^4)；空间复杂度 O (1)

思路 2：使用 unordered_map 记录：（和，出现的次数），先记录 AB 两个数组每个元素相加的元素和的出现次数；O (n^2)

然后遍历所有 CD 数组元素之和的负值在 map 中是否出现过，如果出现说明四个数字相加之和为 0.O (n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map;
        // 记录前两个数组之和出现的次数
        for (int a : nums1) 
            for (int b : nums2) 
                map[a+b]++;

        // 判断剩余两个数组之和
        int result = 0;
        for (int c : nums3) {
            for (int d : nums4) {
                if (map.find(-(c+d)) != map.end()) result += map[-(c+d)];
            }
        }

        return result;
    }
};

时间复杂度 O (n^2)；空间复杂度最坏的情况下两个数组之间的值各不相同看，需要 n 的平方个空间。

赎金信

第 383

收获：之前做过，这里由于 hash 表的长度是固定的（26 个小写字母），所以使用数组更加合适。map 要维护红黑树或者哈希表，而且还要做哈希函数，是费时的

三数之和

第 15

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

思路 1：暴力法：找到和为 0 的三个元素，时间复杂度 O (n^3)；另外找到之后还需要判断不能重复，如果要去重，就需要令比较的两个三元组先排序，才方便比较。

思路 2：采用哈希法：两层 for 循环可以先确定 (a+b) 数值，然后判断 0-(a+b) 是否在数组中出现过，这样整体时间复杂度是 O (n^2)，但是问题是去重，如果先找到所有元素之后再进行去重，那么需要对于结果三元组中进行排序和比较。

思路 3：双指针法，先把数组排序，然后有一层 for 循环，i 从下标 0 的地方开始，同时定一个下标 left 定义在 i+1 的位置上，定义下标 right 在数组结尾的位置上。依然还是在数组中找到 abc 使得 a + b +c =0，我们这里相当于 a = nums [i]，b = nums [left]，c = nums [right]。

接下来如何移动 left 和 right 呢， 如果 nums [i] + nums [left] + nums [right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以 right 下标就应该向左移动，这样才能让三数之和小一些。

如果 nums [i] + nums [left] + nums [right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到 left 与 right 相遇为止。

然后需要注意的是：（1）. 去重的逻辑：去重 a：应该判断与之前的元素是否相同，由于是排序之后的，如果相同说明要么都找不到，要么找到也是重复的；去重 bc，在找到第一对 bc 之后，应该重复判断与他们相邻的是否相等，相等就应该去重。（2）. 找到之后两个指针同时跳变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 先对数组进行排序
        sort(nums.begin(), nums.end());

        vector<vector<int>> result;

        for (int i = 0; i < nums.size(); i++) {
            // 如果第一个元素已经大于0
            // 后面的值都大于第一个元素，所以和一定不可能为0
            if (nums[i] > 0) return result;

            // 对于第一个元素进行去重
            // 如果与之前的元素相同
            // 说明这两次第一个元素都一样，找出的结果都一样
            // 如果与之后的元素进行判断，是允许同一个三元组内元素相同的
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1; // 第二个元素
            int right = nums.size() - 1; // 第三个元素
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    // 此时三元组结果为0
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    
                    // 需要判断后两个元素是否与相邻元素相等
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    while (left < right && nums[left] == nums[left + 1]) left++;

                    // 两个指针同时变化
                    left++;
                    right--;
                }
            }
        } // end for i in range[0, sz)

        return result;
    }
};

时间复杂度 O (n^2)，i 遍历数组，剩下两个指针一起遍历剩下元素；空间复杂度 O (1)

四数之和

18

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路：就是在三数之和的基础上加层循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // 首先对于数组进行排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;

        for (int i = 0; i < nums.size(); i++) {
            int a = nums[i];
            if (a > target && a > 0) break; // 如果第一个元素大于目标值，并且所有元素都为正数

            // 第一个元素去重
            if (i > 0 && a == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.size(); j++) {
                int b = nums[j];
                if (a + b > target && a + b > 0) break;

                // 第二个元素去重
                if (j > i + 1 && b == nums[j - 1]) continue;

                int left = j + 1; // 第三个元素下标
                int right = nums.size() - 1; // 第四个元素下标
                while (left < right) {
                    long sum = long(a) + b + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{a, b, nums[left], nums[right]});
                        // 对于第三个、第四个元素进行去重
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        while (left < right && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--; 
                    }
                } // end of while
            } // end for j
        } // end for i

        return result;
    }
};

时间复杂度 O (n^3)，空间复杂度 O (1)

但是需要注意的是：剪枝的一些细节，比如由于 target 是一个随机值，不能判断第一个元素大于零就直接返回，因为有可能 target 是小于第一个元素的。

错误思路：我的思路是两个双指针，错误的地方是：外层如果用双指针，那么当双指针同时增加时，会漏掉元素

这个问题与之前遇到的同时增加的两个前后指针类似。

思考：我的思路：从外层选两个，从内层选两个，

作者的思路：从 n 个中选一个，从剩下的 n-1 个中选一个，然后双指针选择剩下的两个

注意：两种方式：（1）从 n 中选一个，从剩下的 n-1 中选一个，一共有 n (n-1)/2 中组合

（2）我的两个指针同时从前后增加，那么只有 n/2 种组合

而题目明显是要求第一种方式选择，不要漏掉组合。

注意：双指针是如何把从 n 中选两个的时间复杂度变成 n 的？

（1）从 n 中选两个不同的，正常思路就是 n 的平方；

（2）如果采用双指针，O (n^2) 的解法优化为 O (n) 的解法，因为一次选中不同的两个？

总结

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

哈希函数是把传入的 key 映射到符号表的索引上。

接下来是常见的三种哈希结构：

  • 数组
  • set（集合）
  • map（映射）

使用 set 的理由：

主要因为如下两点：

  • 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
  • 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 否 否 O(log n) O(log n)
std::multiset 红黑树 有序 是 否 O(logn) O(logn)
std::unordered_set 哈希表 无序 否 否 O(1) O(1)

当我们要使用集合来解决哈希问题的时候，优先使用 unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用 set，如果要求不仅有序还要有重复数据的话，那么就用 multiset。

使用 map 的理由：

  • 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
  • set 是一个集合，里面放的元素只能是一个 key，而两数之和这道题目，不仅要判断 y 是否存在而且还要记录 y 的下标位置，因为要返回 x 和 y 的下标。所以 set 也不能用。

C++ 提供如下三种 map：

  • std::map
  • std::multimap
  • std::unordered_map
映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key 有序 key 不可重复 key 不可修改 O(logn) O(logn)
std::multimap 红黑树 key 有序 key 可重复 key 不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key 无序 key 不可重复 key 不可修改 O(1) O(1)

std::unordered_map 底层实现为哈希，std::map 和 std::multimap 的底层实现是红黑树。

在 map 是一个 key value 的数据结构，map 中，对 key 是有限制，对 value 没有限制的，因为 key 的存储方式使用红黑树实现的。

虽然 std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即 key 和 value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map 也是一样的道理。

同理，std::map 和 std::multimap 的 key 也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解），1. 两数之和 中并不需要 key 有序，选择 std::unordered_map 效率更高！