代码随想录-哈希表

哈希表

哈希表基础

哈希表是根据关键码的值而直接进行访问的数据结构。因此数组就是一种哈希表，通过数组下标直接访问数组内容；

哈希函数（HashFunc）

哈希表需要设计一个哈希函数用来把元素内容映射到哈希表中；

哈希碰撞

同时当映射值相同时，称为哈希碰撞，处理哈希碰撞有两种常见的方法：

  1. 线性探索法：发生碰撞时向后寻找可以存放的位置存放；要求哈希表长度一定要大于数据长度，否则就放不下了；
  2. 拉链法：发生碰撞后将新元素链接到原来元素链的尾部，下次查找时通过索引查找元素链表；C++STL的hashtable就使用了拉链法，但是当链表过长时，就相当于对链表进行查找，效率很差，因此STL中的 hashtable 会在元素个数大于哈希表长度时，扩大哈希表长度为原来的二倍并调整到接近的质数，再进行重新建表（rehashing）；

STL容器

  1. unordered_set：键值相同；
  2. unordered_map：键值不同；

有效的字母异位词

LeetCode.242

本题考查对哈希表的理解，数组也是一个哈希表，对于简单的元素类型不需要使用unordered_set或unordered_map，使用数组即可。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isAnagram(string s, string t) {
    int record[26] = {0};  // 相当于一个哈希表
    for(auto c:s){  // 记录s中出现字母的次数
        record[c-'a']++;
    }
    for(auto c:t){  // 记录t中出现字母的次数
        record[c-'a']--;
    }
    for(auto c:record){  // 如果有字母出现次数不为0，说明不是异位词
        if(c!=0){
            return false;
        }
    }
    return true;
}

两个数组的交集（unordered_set用法总结⭐）

LeetCode.349

本题使用哈希表，主要要注意unordered_set的用法：

  1. 初始化：
    1
    2
    3
    4
    5
    6
    unordered_set<int> set1; // 初始化空unordered_set
    unordered_set<int> set2(set1); // 拷贝构造
    unordered_set<int> set3(set2.begin(), set2.end()); // 选取部分元素构造
    // 通过数组构造
    vector<int> nums;
    unordered_set<int> set4(nums.begin(), nums.end());
  2. 查找：find(key) 查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器：
    1
    2
    3
    if(set.find(i)!=set.end()){
         // 找到了i
    }

核心代码：

1
2
3
4
5
6
7
8
9
10
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_set<int> res;
    unordered_set<int> nums1_set(nums1.begin(), nums1.end()); // 初始化
    for(auto i:nums2){
        if(nums1_set.find(i)!=nums1_set.end()){  // 查找
            res.insert(i);
        }
    }
    return vector<int>(res.begin(), res.end());
}

快乐数（⭐⭐）

LeetCode.202

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int getSum(int n){  // 计算新的n
    int sum=0;
    while(n){
        sum+=(n%10)*(n%10);
        n=n/10;
    }
    return sum;
}
bool isHappy(int n) {
    unordered_set<int> sum_set;
    int sum = getSum(n);
    while(sum_set.find(sum)==sum_set.end()){ // 每位之和没出现过
        sum_set.insert(sum); 
        n=sum;
        sum=getSum(n);
        if(sum==1){ // 满足题意
            return true;
        }
    }
    return false;
}

两数之和（哈希法妙啊⭐）

LeetCode.1


核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    unordered_map<int, int> desiredNum_set;
    for(int i=0;i<nums.size();i++){
        int need = target-nums[i];  // 如果当前元素要加一个数得target，应该加哪个数
        if(desiredNum_set.find(need)!=desiredNum_set.end()){
            res.push_back(i);
            res.push_back(desiredNum_set[need]);
        }else{
            desiredNum_set.insert({nums[i], i}); // 添加键值对
        }
    }
    return res;
}

四数相加II（⭐）

LeetCode.454

本题是两数之和的进阶版，大体思路类似，也是用哈希表记录 +后等于零需要+的值，但是由于是四个数组，就两两先相加再判断，需要注意的是要记录相加后结果出现的次数，如前两个数组相加结果为3的数对有2个，后两个数组之和为-3的数组有3个，那么最终结果是2*3=6个数对；

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    unordered_map<int,int> map;
    int res=0;
    for(auto a:nums1){
        for(auto b:nums2){
            int tempSum=a+b;
            map[tempSum]++;  // 特殊用法，如果没有tempSum就insert，有就对值++
        }
    }
    for(auto c:nums3){
        for(auto d:nums4){
            int tempSum=c+d;
            if(map.find(0-tempSum)!=map.end()){
                res+=map[0-tempSum];
            }
        }
    }
    return res;
}

赎金信

LeetCode.383

本题简单，注意不要遇到查找就只想到哈希表（unordered_map等等），数组也是哈希表！ 本题只需要记录26个字母，使用数组又快内存又小！

核心代码：

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
// 数组
bool canConstruct(string ransomNote, string magazine) {
    int record[26] = {0};
    for(auto c:magazine){
        record[c-'a']++;
    }
    for(auto c:ransomNote){
        if(record[c-'a']!=0){
            record[c-'a']--;
        }else{
            return false;
        }
    }
    return true;
}
// 哈希表
bool canConstruct(string ransomNote, string magazine) {
    unordered_map<char, int> map;
    for(auto c:magazine){
        map[c]++;
    }
    for(auto c:ransomNote){
        if(map.find(c)!=map.end()&&map[c]!=0){
            map[c]--;
        }else{
            return false;
        }
    }
    return true;
}

三数之和（用双指针⭐⭐⭐）

LeetCode.15

核心代码：

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
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > 0) {
            return res;
        }
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int left = i + 1;
        int right = nums.size() - 1;
        while (left < right) {
            int tempSum = nums[i] + nums[left] + nums[right];
            if (tempSum > 0) {
                right--;
            } else if (tempSum < 0) {
                left++;
            } else {
                res.push_back({nums[i], nums[left], nums[right]});
                while (right>left&&nums[left] == nums[left + 1]) {
                    left++;
                }
                while (right>left&&nums[right] == nums[right - 1]) {
                    right--;
                }
                left++;
                right--;
            }
        }
    }
    return res;
}

四数之和（⭐⭐）

LeetCode.18

注意不是四数之和等于0，而是等于target，target有可能为负数，剪枝时要注意；

核心代码：

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
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > target && nums[i] >= 0) {
            break;
        }
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[j] + nums[i] > target && nums[j] + nums[i] >= 0) {
                break;
            }
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            int left = j + 1;
            int right = nums.size() - 1;
            while (left < right) {
                long tempSum = nums[i] + nums[j] + nums[left] + nums[right];
                if (tempSum > target) {
                    right--;
                } else if (tempSum < target) {
                    left++;
                } else {
                    res.push_back(
                        {nums[i], nums[j], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
    }
    return res;
}
-[刷题]
#C++
代码随想录-哈希表
https://kenny-hoho.github.io/2024/01/10/代码随想录-哈希表/
作者
Kenny-hoho
发布于
2024年1月10日
许可协议