哈希表:一种存储数据的容器;
可以快速查找某个元素,时间复杂度O(1)
频繁查找某一个数时,我们可以使用哈希表

  1. 创建一个容器(unordered_map)
  2. 数组模拟一个简易哈希表

容器

数据结构unordered_mapmapunorded_setset
实现机理hashRBThashRBT
元素格式key+valuekey+valuekeykey
存储规律无序键升序无序键升序
元素重复键不可,值可键不可,值可不可重复不可重复

两数之和

题目:两数之和

在这里插入图片描述
思路

  • 暴力枚举,初始两个指针 i,j,遍历所有二元组,判断nums[i] + nums[j] == target,时间复杂度:O(N^2)
  • 暴力枚举时间复杂度较高的原因是寻找 target - x 的时间复杂度过高,使用哈希表我们可以将查找的时间复杂度降为O(1),对于每一个 x,我们首先查询哈希表中是否存在target - x

我们可以将元素放入到哈希表中的同时,检查表中是否已经存在当前元素所对应的目标元素,这样就可以避免将元素全部放入到哈希表之后再来二次遍历

C++代码

class Solution 
{
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        unordered_map<int, int> hash; // 【数,下标】
        for(int i = 0; i < numbers.size(); i++)
        {
            if(hash.find(target - numbers[i]) != hash.end())
                return {i, hash[target - numbers[i]]};

            hash[ numbers[i] ] = i;
        }
        
        return {};
    }
};

判定是否互为字符重排

题目:判定是否互为字符重排

在这里插入图片描述
思路

  • 如果两长度不相等,直接返回fasle
  • 创建一个hash表,对于s1我们添加到hash表中,对于s2中的每个字符如果hash中存在,那么我们删除一个,最后单独遍历一遍hash表,如果其值不等于零也就意味值s1或s2中元素数量不匹配,也就不发重排。

C++代码

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

        unordered_map<char, int> hash;
        for(auto ch : s1) hash[ch]++;
        for(auto ch : s2) hash[ch]--;
    
        for(auto x : hash) 
            if(x.second != 0)
                return false;

        return true;
    }

};

存在重复元素

题目:存在重复元素

在这里插入图片描述
思路

  • 创建一个hash表,插入元素;
  • 遍历hash表,如果某个元素个数不等于1,返回true;遍历完后如果没有返回,则返回false

C++代码

class Solution 
{
public:
    bool containsDuplicate(vector<int>& nums) 
    {
        unordered_map<int, int> hash;
        for(auto x : nums)
            hash[x]++;

        for(auto x : hash)
            if(x.second != 1) 
                return true;

        return false;
    }
};

存在重复元素 II

题目:存在重复元素 II

在这里插入图片描述
思路

  • 和两数之和一样,只需在遇到相同元素时相减判断;

C++代码

class Solution 
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        // 【数,下标】
        unordered_map<int, int> hash;

        int n = nums.size();
        for(int i = 0; i < n; i++)
        {
            // 如果当前元素已经在 hash 中存在
            if(hash.count(nums[i]))
            {
                // 判断下标是否满足要求
                if(i - hash[nums[i]] <= k)
                    return true;
            }
                            
            hash[nums[i]] = i;
        }

        return false; // 遍历完数组没有发现符合条件的重复元素,返回 false
    }
};

字母异位词分组

题目: 字母异位词分组

在这里插入图片描述
思路

  • 判断两个字符串是否为字母异位词(排序)
  • unordered_map<string, vector<string>> hash;

C++代码

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

        vector<vector<string>> ret;
        for(auto& [k, v] : hash)
        {
            ret.push_bacck(y);
        } 

        return ret;
    }
};

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部