【Leetcode每日一刷】哈希表|纲领、242.有效的字母异位词、349. 两个数组的交集

纲领

🔗代码随想录理论部分
关于哈希表这个数据结构就不再重复讲了，下面对几个关键点记录一下：

• 哈希碰撞
  解决方法1：拉链法
  解决方法2：线性探测法

下面针对做题要用到的三种结构讲一下（也是重复造轮子了算是）

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）（元素不能重复）
• map(映射)

unordered_set在C++11的时候被引入标准库了，而hash_set并没有，所以建议还是使用unordered_set比较好，这就好比一个是官方认证的，hash_set，hash_map 是C++11标准之前民间高手自发造的轮子。

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

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

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

242.有效的字母异位词

力扣题目链接

🦄解题思路：

这题很容易看出来是个哈希，把26个字母映射到26长度的数组中，数组中的值表示元素出现的个数。遍历完两个字符串完成哈希后，再把两个字符串的哈希数组进行比较是否一样即可。

✅正确代码：

class Solution {
public:
    bool isAnagram(string s, string t) {
        int a[26] = {0};
        int b[26] = {0};

        for(int i = 0; i < s.size(); i++) a[s[i] -'a'] ++ ;
        for(int i = 0; i < t.size(); i++) b[t[i] -'a'] ++ ;

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

349. 两个数组的交集

题目链接

🦄解题思路：

这题当然也是哈希，但是在数据结构上再用数组就不太合适了；因为key比较分散，稀疏，使用数组用作哈希表浪费空间。这里使用数据结构：set

此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：

• std::set
• std::multiset
• std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set

✅正确代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        int hash[1005] = {0}; // 默认数值为0
        for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
            hash[num] = 1;
        }
        for (int num : nums2) { // nums2中出现话，result记录
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

其实呢，Nums1哈布哈希无所谓，只要在nums1中发现nums2元素，则加进不可重复的set即

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            vector<int>::iterator it = find(nums1.begin(), nums1.end(), num);
            if (it != nums1.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

补充

那有同学可能问了，遇到哈希问题我直接都用set不就得了，用什么数组啊。

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。