【算法-哈希表1】哈希表有什么用? 来看看有效的字母异位词和两数组的交集.

今天，带来哈希相关算法的讲解。文中不足错漏之处望请斧正！

理论基础点这里

有效的字母异位词

1. 思路

暴力的解法，需要两层for循环，同时还要记录字符是否重复出现，很明显时间复杂度是 O(n^2)。

其实可以用哈希表来解决，哈希就是查找某元素在某集合中是否出现的好办法。

因为只涉及到26个小写字母，所以数组就够用。建立字符和数组下标的映射，记录字符出现次数。

数组下标代表字符
数组下标对应的值代表出现此处

遍历s和t，记录每个字符出现次数
遍历数组，查看某字符在两个字符串中的出现次数是否一样

在这里插入图片描述
*动图来源：代码随想录

这样是O(2n+26)，即O(n)的时间复杂度。

2. 参考代码

class Solution {
public:
    // 字母异位词:若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
    bool isAnagram(string s, string t) {
		//cnt的[0,25]下标本身对应['a','z']
		//cnt的[0,25]的值对应['a','z']的出现次数
        int cnt[26] = {0};
		
		// 遍历两个字符串, 求其元素出现次数, 统计时s对于cnt是加操作, t对于cnt是减操作
		// 如果二者字符出现次数相同, 则cnt的每个元素都应该是0
        for (char &ch : s) ++cnt[ch - 'a'];
        for (char &ch : t) --cnt[ch - 'a'];

        for (int i = 0; i < 26; ++i) if (cnt[i] != 0) return false;

        return true;
    }
};

两个数组的交集

1. 思路

两数组的交集，就是在两数组都出现过的元素。

凡是看到判断集合中某元素是否出现或者统计次数，那就很可能用到哈希表。因为哈希表通过key值和位置建立映射，可以通过key值快速找到对应元素，完成高效的读写。

那我们用什么数据结构来实现哈希表呢？这里用set和数组都可以。因为题目规定，元素大小小于1000，所以数组也能用。

那数组什么时候不合适呢？

当数据分布不集中，就不适合使用数组了，比如存储两个整数0和99999999，需要开辟10000000个int的数组。极大浪费空间。

什么时候数组合适呢？

恰好就是数据分布集中的时候，我们首选数组。因为set和map都是有开销的，作为STL的容器，他需要很多辅助空间来实现功能。说白了就是更复杂，但适用大多数场景。而数组实现的哈希表，场景比较有限；但开销很小，性能高些。

尽管unordered_set和unordered_map的读写复杂度是O(1)，但是哈希函数的映射等操作也是有消耗的，数据量大的时候和数组比起来差距还是比较明显的。

但数组在上期用过了，这次主要讲解set。根据题意，我们使用unordered_set最合适，因为它的读写复杂度是O(1)。

2. 参考代码

set实现

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result; // 存放交集结果, 用set存储可以去重
        unordered_set<int> nums1Set(nums1.begin(), nums1.end());

        for (int &num2 : nums2) {
            if (nums1Set.find(num2) != nums1Set.end()) {
                result.insert(num2);
            }
        }

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

数组实现

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        bool appeared[1001] = {false}; //保证整数1000也能映射进来
        unordered_set<int> result;
        for(auto &e : nums1) {
            appeared[e] = true;
        }
        for(auto &e : nums2) {
            if(appeared[e] == true) result.insert(e);
        }
        return vector<int>(result.begin(), result.end());
    }
};