【算法】哈希表

快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

哈希表，其作用在于快速查找特定的值，从而优化时间复杂度，但会增加空间复杂度，典型以空间换时间。在做题的过程中，可以用数组模拟（数据范围小且数据为正），也可以用容器实现。

一、两数之和

思路：

1. 暴力解法：我们每次先固定一个数，再查找该数之前的所有数（这里的思路和普通暴力略有不同）
2. 利用哈希表优化：每次遍历完一个数，将其存入哈希表，再次查找时就不用依次往前遍历
3. 为什么之前的暴力策略不好用了呢？因为按照之前的暴力策略，要事先将所有的数都存入哈希表中，再在哈希表中进行查找。同时，因为有可能查找到自身元素，所以还要额外判断排除这种情况。
   

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int, int> hash;//<nums[i], i>
        for(int i=0; i<nums.size(); i++)
        {
            int n = target - nums[i];
            if(hash.count(n)) return {hash[n], i};
            hash[nums[i]] = i;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、判断字符重排

思路：

1. 先判断两个字符串长度是否相等，若不相等则肯定不能重排
2. 利用哈希表，统计每个字母出现的个数
3. 遍历s1，增加字符个数，遍历s2，减少字符个数，当字符个数为负数，则不能重排（同时这样可以只使用一个哈希表）
4. 若最后没有字符个数为负数，则代表也没有字符个数为正（因为两个字符串长度相等，拥有的字符数相等），则代表对应的字符数相等

class Solution
{
public:
    bool CheckPermutation(string s1, string s2)
    {
        if(s1.size() != s2.size()) return false;//优化

        int hash[26] = { 0 };
        for(auto ch : s1) hash[ch - 'a']++;
        for(auto ch : s2)
        {
            hash[ch - 'a']--;
            if(hash[ch - 'a'] < 0) return false;//优化
        }

        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、存在重复元素

思路：

1. 和两数之和的策略相似
2. 先在哈希表中查找是否存在该数
3. 再将该数存入哈希表

class Solution
{
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_set<int> hash;
        for(auto x : nums)
        {
            if(hash.count(x)) return true;
            hash.insert(x);
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

四、存在重复元素 ||

思路：

1. 与存在重复元素思路相似，只不过增加了一个条件
2. 所以哈希表要多存储元素的下标
3. 先判断哈希表内是否存在符合条件的值，再将该值和下标存入哈希表
4. 值得注意的是，本题要求的是距离<=k，所以存入哈希表可以大胆覆盖距离更远的相同元素，但是如果改成>k的话，这种策略就失效了

class Solution
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;//<nums[i], i>
        for(int i=0; i<nums.size(); i++)
        {
            int x = nums[i];
            if(hash.count(x) && i - hash[x] <= k) return true;
            hash[x] = i;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

五、字母异位词分组

思路：

1. 通过本题，我们可以了解高级语言中容器和泛型编程的强大之处
2. 创建哈希表，存储字符串和字符串数组
3. 对于每一个单词，我们先对其排序，这样所有的异位词都对应同一个字符串
4. 再将排序后的字符串，作为哈希表的键值，其对应的字符串数组添加原字符串
5. 最后，再遍历一遍哈希表，把字符串数组依次添加到ret中

class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string>> hash;
        for(auto& str : strs)
        {
            string s = str;
            sort(s.begin(), s.end());
            hash[s].push_back(str);
        }

        vector<vector<string>> ret;
        for(auto& kv : hash) ret.push_back(kv.second);
        return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

真诚点赞，手有余香