代码随想录1刷—哈希表篇

哈希表理论基础

• 哈希表是根据关键码的值而直接进行访问的数据结构。

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

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

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

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

哈希函数

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

一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值。

为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作。

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

哈希碰撞

拉链法

把发生冲突的元素都被存储在链表中。

拉链法重点在于选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。

（数据规模是dataSize， 哈希表的大小为tableSize）

常见的三种哈希结构

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

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

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

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，但是std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

242. 有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for(int i = 0;i < s.size();i++){
            record[s[i]-'a']++;
        }
        for(int i = 0;i < t.size();i++){
            record[t[i]-'a']--;
        }
        for(int i = 0;i < 26;i++){
            if(record[i] != 0){
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

拓展类似题：383. 赎金信

本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点。

• 第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
• 第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要

暴力枚举

第一个思路其实就是暴力枚举了，两层for循环，不断去寻找，但这里时间复杂度是比较高的，而且里面还有一个字符串删除也就是erase的操作，也是费时的，更好的方案是哈希。

// 时间复杂度: O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for (int i = 0; i < magazine.length(); i++) {
            for (int j = 0; j < ransomNote.length(); j++) {
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
            return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

哈希

因为题目所只有小写字母，那可以采用空间换取时间的哈希策略， 用一个长度为26的数组还记录magazine里字母出现的次数。然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。依然是数组在哈希法中的应用。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        for (int i = 0; i < magazine.size(); i++) {
            record[magazine[i] - 'a']++;
        }
        for (int i = 0; i < ransomNote.size(); i++) {
            record[ransomNote[i] - 'a']--;
            if(record[ransomNote[i] - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

拓展类似题：49. 字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        unordered_map<string,vector<string>> map;
        for(int i = 0;i<strs.size();i++){
            string key = strs[i];
            sort(key.begin(), key.end());
            map[key].emplace_back(strs[i]);
        }
        //声明变量时根据初始化表达式自动推断该变量的类型，方便地获取复杂的类型
        for (auto it = map.begin(); it != map.end(); it++) {
            result.emplace_back(it->second);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

for (String str : strs)

for(int i=0;i<strs.length;i++){
  String str=strs[i];
}
等同于：
    for (String str : strs)
1
2
3
4
5

emplace_back()

emplace_back() 在容器尾部添加一个元素，调用构造函数原地构造，不需要触发拷贝构造和移动构造。 因此比 push_back () 更加高效。

push_back()：先向容器尾部添加一个右值元素(临时对象)，然后调用构造函数构造出这个临时对象，最后调用移动构造函数将这个临时对象放入容器中并释放这个临时对象。**注：**最后调用的不是拷贝构造函数，而是移动构造函数。因为需要释放临时对象，所以通过std::move进行移动构造，可以避免不必要的拷贝操作。

拓展类似题：438. 找到字符串中所有字母异位词

滑动窗口！

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char,int>need,window;
        for(char c:p) need[c]++;
        int left = 0;
        int right = 0;
        int valid = 0;
        vector<int> res;
        while(right<s.size()){
            char c = s[right];
            right++;  
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]){
                    valid++;
                }
            }
            while(right - left>=p.size()){
                if(valid == need.size()){
                    res.push_back(left);
                }
                char d = s[left];
                left++;
                if(need.count(d)){
                    if(window[d] == need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return res;
    }
};
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

349. 两个数组的交集

find(key)

查找值为key的元素，如果找到，则返回一个指向该元素的正向迭代器；如果没找到，则返回一个与end()方法相同的迭代器。所以搜索时应写nums.find(num)!=nums.end()

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

用数组还是set？

**使用数组来做哈希的题目，是因为题目都限制了数值的大小。**而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。主要因为如下两点：

• 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
• 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

但遇到哈希问题也不能直接无脑用set，需要判断用数组还是用set合适，直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。不要小瞧这个耗时，在数据量大的情况，差距是很明显的。

相似拓展题：350. 两个数组的交集 II

哈希表（法一）

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> map;
        vector<int> ans;
        if(nums1.size()>nums2.size()){
            return intersect(nums2,nums1);
        }   //为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
        for(int num:nums1){
            map[num]++;
        }
        for(int num:nums2){
            if(map.count(num)){
                ans.push_back(num);
                map[num]--;
                if (map[num] == 0) {
                    map.erase(num);
                }
            }
        }
        return ans;
    }
};
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:
      vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
          sort(nums1.begin(), nums1.end());
          sort(nums2.begin(), nums2.end());
          int length1 = nums1.size(), length2 = nums2.size();
          vector<int> intersection;
          int index1 = 0, index2 = 0;
          while (index1 < length1 && index2 < length2) {
              if (nums1[index1] < nums2[index2]) {
                  index1++;
              } else if (nums1[index1] > nums2[index2]) {
                  index2++;
              } else {
                  intersection.push_back(nums1[index1]);
                  index1++;
                  index2++;
              }
          }
          return intersection;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22

进阶问题

• 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
  • 使用哈希表（法一），nums2 只关系到查询操作，所以每次读取nums2 的一部分数据并进行处理即可。

202. 快乐数

题目中说了会 无限循环，那么也就是说**求和的过程中，sum会重复出现，这对解题很重要！**当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。判断sum是否重复出现就可以使用unordered_set。

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

class Solution {
public:
    int getSum(int n){
        int sum = 0;
        while(n){
            sum += (n % 10) * (n % 10);
            n/=10;
        }
        return sum;
    }

    bool isHappy(int n) {
        unordered_set<int> set;
        while(1){
            int sum = getSum(n);
            if (set.find(sum) != set.end()) {
                return false;
            }else {
                set.insert(sum);
            }
            if(sum == 1) return true;
            n = sum;
        }
    }
};
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

1. 两数之和

用数组、set还是map？

使用数组和set来做哈希法的局限如下：

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

此时就要选择另一种数据结构：map，map是一种<key, value>的结构，本题可以用key保存数值，用value在保存数值所在的下标。所以使用map最为合适。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int i = 0;i<nums.size();i++){
            if(map.find(target-nums[i])!=map.end()){
                return {map.find(target-nums[i])->second,i};
            }
            map.insert(pair<int,int>(nums[i],i));
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

454. 四数相加 II

这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以区别于题目18. 四数之和，题目15.三数之和，使用哈希比较简单！

而0015.三数之和，0018.四数之和并不合适使用哈希法，采用排序+双指针会更舒适不易出错，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。

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 ans = 0;
        for(int c:nums3){
            for(int d:nums4){
                if(map.find(0-(c+d))!=map.end()){
                    ans+=map[0-(c+d)];
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

15. 三数之和（直接cv的，后补）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                    // 当前元素不合适了，可以去重
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                    // 不合适，去重
                    while (left < right && nums[left] == nums[left - 1]) left++;
                } else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};
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
46
47
48
49
50
51
52
53
54

18. 四数之和（直接cv的，后补）

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
	    // 剪枝处理
            if (nums[k] > target && (nums[k] >= 0 || target >= 0)) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
	    	// 2级剪枝处理
		if (nums[k] + nums[i] > target && (nums[k] + nums[i] >= 0 || target >= 0)) {
		    break;
		}
		
                // 正确去重方法
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
                        right--;
                        // 当前元素不合适了，可以去重
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if (nums[k] + nums[i]  < target - (nums[left] + nums[right])) {
                        left++;
                        // 不合适，去重
                        while (left < right && nums[left] == nums[left - 1]) left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 去重逻辑应该放在找到一个四元组之后
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};
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
46
47
48
49
50
51
52
53
54