哈希表(使用C++实现)

😲示例

主要使用map和set, 如果是键值对结构就使用map, 如果不是键值对结构但是需要去重, 就使用set

unordered_set是C++标准库中的一个容器，用于存储唯一的元素集合，所以需要去重的数据可以用它来存, 元素的存储顺序是无序的。下面是unordered_set的基本用法、常见函数和遍历方法：

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
// 1. 包含头文件：
#include <unordered_set>


// 2. 声明和初始化unordered_set：
std::unordered_set<int> mySet; // 声明一个空的unordered_set
std::unordered_set<int> mySet = {1, 2, 3}; // 声明并初始化一个unordered_set
std::vector<int> vec = {1, 2, 3, 4, 5};
std::unordered_set<int> mySet(vec.begin(), vec.end()); // 使用迭代器范围构造unordered_set
std::unordered_set<int> mySet1 = {1, 2, 3};
std::unordered_set<int> mySet2(mySet1); // 使用拷贝构造函数创建一个与已有unordered_set相同的副本


// 3. 插入元素：
mySet.insert(4); // 插入单个元素
mySet.insert({5, 6, 7}); // 插入多个元素


// 4. 删除元素：
mySet.erase(3); // 删除指定元素
mySet.clear(); // 清空unordered_set


// 5. 查找元素：
auto it = mySet.find(2); // 查找指定元素，返回迭代器
// 如果没有找到就会返回最后一个的下一个指针
if (it != mySet.end()) {
    // 找到了元素
} else {
    // 没有找到元素
}


// 6. 判断元素是否存在：
if (mySet.count(3) > 0) {
    // 元素存在
} else {
    // 元素不存在
}


// 7. 获取unordered_set的大小：
int size = mySet.size(); // 返回unordered_set中元素的个数


// 8. 遍历unordered_set：
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
    // 使用迭代器访问unordered_set中的元素
}

// 或者使用范围-based for循环（C++11及以上版本）
for (const auto& element : mySet) {
    // 使用元素访问unordered_set中的元素
}

unordered_map的用法和常用函数

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
#include <iostream>
#include <unordered_map>

int main() {
    // 创建一个unordered_map
    std::unordered_map<int, std::string> myMap;

    // 插入键值对
    myMap.insert({1, "apple"});
    myMap[2,"orange"];
    

    // 访问元素
    std::cout << "Value at key 2: " << myMap[2] << std::endl;

    // 检查键是否存在, 使用count()
    if (myMap.count(2) > 0) {
        std::cout << "Key 2 exists" << std::endl;
    }

    // 检查键是否存在, 使用find()
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Key 2 found. Value: " << it->second << std::endl;
    } else {
        std::cout << "Key 2 not found." << std::endl;
    }

    // 修改元素的值
    myMap[1] = "grape";

    // 删除元素
    myMap.erase(2);

    // 遍历unordered_map, 指针的first和second可以返回键和值
    for (const auto& pair : myMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

注意使用了两种查找auto, auto it = myMap.find(2);返回的是迭代器指针, 如果需要成员变量需要使用->, 而const auto& pair : myMap使用了迭代器的引用类型, 使用指针初始化引用类型, 引用类型的使用和原变量一样, 直接使用.

🤔一些疑问解答

const auto& pair : myMap中必须加const吗?

在遍历unordered_map时，使用const auto& pair : myMap是一种常见的做法，但并不是必须的
使用const auto&可以确保你不会意外地修改unordered_map中的元素。这是一种安全的做法
如果需要再遍历的过程中修改或删除一些值, 那么可以使用auto&而不是const auto&

为什么有的哈希表题目并没有用哈希表来做而是用数组?

如果题目中确实需要查每个元素, 但是元素的取值范围并不大, 而且索引可以直接算出来不需要遍历, 那么就可以直接用数组, 比如力扣题目242

💪力扣刷题

242. 有效的字母异位词

力扣传送门

这个需要一个哈希表记录所有字母的出现次数, 但是由于题目中只出现26个字母, 所以也可以直接使用数组记录字母出现次数

如果s中出现字母, 则再记录表中+1, 如果t表中出现字母, 则再记录表中-1, 最后只需要记录表中有没有非0元素

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

349. 两个数组的交集

力扣传送门

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) {
        // 收集nums1中出现的所有数并去重
        unordered_set<int> data(nums1.begin(),nums1.end());
        // 结果集合也不能有重复, 所以先使用unordered_set, 随后转换为vector
        unordered_set<int> rs;
        int len = nums2.size();
        // 遍历nums2, 如果找到了重复元素, 那么加入结果集合
        for(int i=0; i<len; i++){
            if(data.find(nums2[i])!=data.end())
                rs.insert(nums2[i]);
        }
        // 转换为vector并返回
        return vector<int>(rs.begin(),rs.end());
    }
};

202. 快乐数

力扣传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isHappy(int n) {
        int new_n=n, sum;           // 用于保存每一次的数字本身和数字各位上的平方和
        unordered_set<int> sums;    // 用于保存出现过的数字, 防止无限循环导致超时
        while(new_n!=1){            // 只要没出现1就接着算
            int k;                  // k用于取出各个位上的数字
            sum = 0;                // sum用于存数字各个位上的平方和
            while(new_n!=0){        // 没去完数字所有位就接着取
                k = new_n%10;
                sum+=k*k;
                new_n/=10;
            }
            if(sums.find(sum)!=sums.end())  // 如果发现了重复
                return false;               // 返回false
            else                            // 否则就把这一次的数字存进集合中
                sums.insert(sum);
            new_n = sum;                    // 这一次的平方和是下一次的数字
        }
        return true;                        // 如果跳出循环说明找到了1
    }
};

1. 两数之和

力扣传送门

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) {
        vector<int> rs(2);              // 用于保存结果
        unordered_map<int,int> my_map;  // 用于保存没一个数字的下标
        int len = nums.size();          // 存一下大小, 避免反复访问
        for(int i=0; i<len; i++)        // 存储没一个数的下标
            my_map[nums[i]] = i;        // 数字为键, 下标为值
        for(int i=0; i<len; i++){       // 查找每一个数被target减去的差在不在数组中
            auto it = my_map.find(target-nums[i]);  // 获取差的下标
            if(it!=my_map.end() && it->second!=i){  // 如果存在差, 并且不是自己
                rs[0] = i;                          // 存本身的下标
                rs[1] = it->second;                 // 存差的下标
                break;                              // 跳出循环
            }
        }
        return rs;;                                 // 返回结果
    }
};

454. 四数相加 II

力扣传送门

先统计前两个数组的所有和, 用map, 键是和, 值是和出现的次数
再统计后两个数组的所有和, 不用新建map, 直接查之前的那个map里有没有相反数, 有的话结果就加上对应的情况数目

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> my_map;
        for(int i:nums1){
            for(int j:nums2){
                my_map[i+j]++;
            }
        }
        int count = 0;
        for(int i:nums3){
            for(int j:nums4){
                if(my_map.find(0-i-j)!=my_map.end()){
                    count+=my_map[0-i-j];
                }
            }
        }
        return count;
    }
};

383. 赎金信

力扣传送门

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

15. 三数之和

力扣传送门

1
// 还没做