【算法系列】哈希表

哈希表总结

leetcode题目

一、两数之和

二、判定是否互为字符重排

三、存在重复元素

四、存在重复元素 II

五、字母异位词分组

六、在长度2N的数组中找出重复N次的元素

七、两个数组的交集

八、两个数组的交集 II

九、两句话中的不常见单词

哈希表总结

1.存储数据的容器

2.需要快速查找数据时，用哈希表

3.当题目中给定的字符串或者数组只包含小写字母或数据范围是0~100/1000等等时，可以用数组模拟哈希表

4.当数据范围是负数到正数时，不建议用数组模拟哈希表，因为还要加一个数转化之后进行映射，建议直接使用STL容器

leetcode题目

一、两数之和

1. 两数之和 - 力扣（LeetCode）https://leetcode.cn/problems/two-sum/1.题目解析

给定数组与target, 返回和为target的两个元素下标

2.算法分析

解法一: 暴力枚举

策略一: 先固定一个数，然后依次与该数之后的数相加

策略二: 先固定一个数，然后依次与该数之前的数相加

解法二: 使用哈希表优化

暴力解法之所以慢，以策略二为例, 是因为枚举到nums[i]时，要在这个位置之前都遍历一下，看哪个数字等于target-nums[i], 所以如果我们枚举到nums[i]时，前面的数字都被扔进了哈希表中，我们就可以以O(1)的时间复杂度找到结果~

注意：如果是用哈希表暴力枚举策略一，最好是倒着遍历~

3.算法代码

暴力枚举策略一:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        for(int i = 0; i < nums.size(); i++)
        {
            for(int j = i + 1; j < nums.size(); j++)
            {
                if(nums[i] + nums[j] == target)
                    return {i, j};  
            }
        }
        return {-1, -1};
    }
};

暴力枚举策略二:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        for(int i = 1; i < nums.size(); i++)
        {
            for(int j = i - 1; j >= 0; j--)
            {
                if(nums[i] + nums[j] == target)
                    return {i, j};  
            }
        }
        return {-1, -1};
    }
};

哈希表优化策略一:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        unordered_map<int, int> hash; //<nums[i], i>
        for(int i = nums.size()-1; i >= 0; i--)
        {
            int x = target - nums[i];
            if(hash.count(x)) 
                return {hash[x], i};
            hash[nums[i]] = i;
        }
        return {-1, -1}; //照顾编译器
    } 
};

哈希表优化策略二:

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 x = target - nums[i];
            if(hash.count(x)) 
                return {hash[x], i};
            hash[nums[i]] = i;
        }
        return {-1, -1}; //照顾编译器
    } 
};

二、判定是否互为字符重排

面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）https://leetcode.cn/problems/check-permutation-lcci/1.题目解析

给定两个字符串，判断一个字符串是否能够通过重排变成另一个字符串

2.算法分析

如果s1能够重排形成s2, 那么s1每个字符出现的个数和s2对应字符出现的个数是相等的！于是可以使用哈希表，而题目中说字符串只有小写字母，因此用数组模拟哈希表即可。所以解法就是用两个哈希表，然后判断哈希表是否相等即可；

优化1: 只使用一个哈希表统计s1中字符个数，然后遍历第二个字符串，把对应字符在哈希表中的个数--，如果--之后是负数了，返回false即可

优化2: 两个字符串的长度不相等，直接返回false即可

3.算法代码

class Solution {
public:
    bool CheckPermutation(string s1, string s2)
    {
        //优化
        if(s1.size() != s2.size()) 
            return false;
            
        int hash[26] = {0};
        for(auto& e : s1)   
            hash[e - 'a']++;
        for(auto& e : s2)
        {
            hash[e - 'a']--;
            if(hash[e - 'a'] < 0)
                return false;
        }
        return true;
    }
};

三、存在重复元素

217. 存在重复元素 - 力扣（LeetCode）https://leetcode.cn/problems/contains-duplicate/1.题目解析

数组中存在重复元素返回true, 不存在重复元素返回false

2.算法分析

使用哈希表解决问题~

3.算法代码

unordered_map:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) 
    {
        unordered_map<int, int> hash;
        for(auto& e : nums)
        {
            hash[e]++;
            if(hash[e] > 1) 
                return true;
        }
        return false;
    }
};

unordered_set:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) 
    {
        unordered_set<int> hash;
        for(auto& e : nums)
        {
            if(hash.count(e)) 
                return true;
            else
                hash.insert(e);
        }
        return false;
    }
};

四、存在重复元素 II

219. 存在重复元素 II - 力扣（LeetCode）https://leetcode.cn/problems/contains-duplicate-ii/1.题目解析

判断数组中是否存在两个相同的元素，并且下标的绝对值小于等于k

2.算法分析

从前向后遍历数组，同时将遍历过的元素和下标绑定扔进哈希表，遍历的同时判断是否满足题意即可

小细节：nums = [1 0 2 1 3 1 4], k =2, 当遍历到第2个1时，发现下标i-j=3>k, 不满足题意，此时将1和下标3绑定扔进哈希表覆盖之前的 <1, 0> 是完全可以的, 因为题目求的是 i-j <= k, 因此i和j越近越好，因此我们可以直接覆盖原先的值~

3.算法代码

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++)
        {
            if(hash.count(nums[i]) && i-hash[nums[i]] <= k)
                return true;
            hash[nums[i]] = i;
        }
        return false;
    }
};

五、字母异位词分组

49. 字母异位词分组 - 力扣（LeetCode）https://leetcode.cn/problems/group-anagrams/description/1.题目解析

给一个字符串数组，将所有的字母异位词放到一组，返回一个二维数组

2.算法分析

1.判断两个字符串是否是字母异位词(可以用哈希表，但是代码不好写，我们选择直接排序, 排序结果一样，那就互为字母异位词)

2.将相同的字母异位词分组 --- 借助哈希表 <string, string[ ]>, 哈希表第一个位置存储排序后的字符串，第二个存储一个字符串数组；

3.算法代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        unordered_map<string, vector<string>> hash;
        //1.将所有的字母异位词分组
        for(auto& s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        //2.提取结果
        vector<vector<string>> ret;
        for(auto& [x, y] : hash)
        {
            ret.push_back(y);
        }
        return ret;
    }
};

六、在长度2N的数组中找出重复N次的元素

961. 在长度 2N 的数组中找出重复 N 次的元素 - 力扣（LeetCode）https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/description/1.题目解析

我们在深剖一下题意，本质就是只有1个数重复出现了，其他数都只出现了一次

2.算法分析

思路一: 遍历数组，将当前元素和出现次数丢进哈希表，当某个数出现次数 == n时，返回该数

思路二: 遍历数组，进循环先判断该数是否已经存在，存在就直接返回，不存在就将该数丢进哈希表

3.算法代码

思路一:

class Solution {  
public:  
    int repeatedNTimes(vector<int>& nums)  
    {  
        size_t n = nums.size() / 2;
        unordered_map<int, int> hash; // [x, count]  
        for(auto& e : nums)  
        {  
            hash[e]++;  
            if(hash[e] == n)   
                return e;  
        }  
        return -1;
    }  
};

思路二:

class Solution {  
public:  
    int repeatedNTimes(vector<int>& nums)  
    {  
        unordered_map<int, int> hash; // [x, count]  
        for(auto& e : nums)  
        {  
            if(hash[e] == 1) // 只需要检查是否已经存在（即重复了一次）  
                return e;  
            hash[e]++;  
        }  
        return -1;
    }  
};

七、两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-arrays/submissions/

1.题目解析

返回两个数组的交集（输出结果的每个元素要是唯一的）

2.算法分析

将两个数组元素扔进两个 unordered_set 哈希表进行去重，然后遍历其中一个哈希表，看该哈希表中的元素在另一个哈希表中是否存在，存在就插入到结果数组中！

3.算法代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<int> ret;
        unordered_set<int> hash1;
        unordered_set<int> hash2;
        for(auto& e : nums1) //对nums1元素去重
            hash1.insert(e);
        for(auto& e : nums2) //对nums2元素去重
            hash2.insert(e);

        for(auto& e : hash1)
            if(hash2.count(e))
                ret.push_back(e);
        return ret;
    }
};

八、两个数组的交集 II

350. 两个数组的交集 II - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-arrays-ii/1.题目解析

返回两个数组的交集 (结果中可以有重复元素)

2.算法分析

定义一个哈希表 unordered_map，遍历第一个数组，将数组元素和出现的个数绑定扔进哈希表, 然后遍历第二个数组，元素在哈希表中出现，就插入到结果数组中，然后将该元素在哈希表中的个数--即可

3.算法代码

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) 
    {
        unordered_map<int, int> hash;
        for(auto& e : nums1)
            hash[e]++;

        vector<int> ret;
        for(auto& e : nums2)
        {
            if(hash[e])
            {
                ret.push_back(e);
                hash[e]--;
            }
        }
        return ret;
    }
};

九、两句话中的不常见单词

884. 两句话中的不常见单词 - 力扣（LeetCode）https://leetcode.cn/problems/uncommon-words-from-two-sentences/description/

1.题目解析

返回两句话中互相在另一句话中没有出现的所有单词

2.算法分析

可以将两个字符串合在一起，提取出所有的单词同时扔进哈希表统计单词出现的次数，然后遍历一遍哈希表，出现次数为1的单词就是我们要的结果

3.算法代码

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) 
    {
        //1.将所有的单词提取出来
        vector<string> words;
        string tmp;
        string s = s1 + ' ' + s2;
        unordered_map<string, int> hash;
        for(size_t i = 0; i <= s.size(); i++)
        {
            if(s[i] != ' ' && i != s.size())
                tmp += s[i];
            else
            {
                words.push_back(tmp);
                hash[tmp]++;
                tmp.clear();
            }
        }

        //2.从哈希表中提取结果
        vector<string> ret;
        for(auto [x, y] : hash)
            if(y == 1)
                ret.push_back(x);
        return ret;
    }
};