算法讲解之哈希表

admin管理员组

文章数量:1794759

算法讲解之哈希表

哈希表简介：

通过以下几个问题来解释~

1、哈希表是什么？

存储数据的容器。

2、有什么用？

“快速”查找某个元素。时间复杂度O(1) 空间复杂度O(N)

3、什么时候使用哈希表

频繁的查找某个数时。

4、怎么用哈希表

第一种就是直接使用哈希表的容器。

第二种利用数组实现（在数据范围很小的情况下，比如字符）

---

下面就开始实战！

第一题、1. 两数之和

解析：

按正常算法时间复杂度为O(N^2)，利用哈希就是以空间换时间的算法。时间和空间的复杂度都是O(N)。

将数组中的数存储进入哈希，然后用count函数去寻找，如果存在，直接返回结果。

原码：

代码语言：javascript代码运行次数：0运行复制

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 {i,hash[x]};
            //插入哈希表
            hash[nums[i]] = i;
        }
        //照顾编译器
        return {-1,-1};
    }
};

第二题：判定是否互为字符重排

解析：

本题也是用空间换时间复杂度的算法。

该题可以不用库里的容器，自己用数组模拟哈希，因为本题最多只有26个字符，数据范围较小。

然后遍历第一个字符串，进行模拟++，再去遍历第二个字符串，看字符出现的次数是否一致。

原码：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        //先判断字符串不相等特殊情况
        if(s1.size() != s2.size()) return false;  
        //直接模拟哈希表
        int hash[26] = {0};
        //先统计第一个字符串信息
        for(int i = 0;i<s1.size();i++)
        {
            hash[s1[i] - 'a']++;
        }
        //扫描第二个字符串，看看是否能重排
        for(int i = 0;i<s2.size();i++)
        {
            hash[s2[i] - 'a']--;
            if(hash[s2[i] - 'a'] < 0) return false;
        }
        return true;
    }
};

第三题、49. 字母异位词分组

题目描述：

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

代码语言：javascript代码运行次数：0运行复制

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解析：

本道题就体现了哈希表的强大之处，我们可以将哈希表存储为： unordered_map<string,vector<string>> hash;//<first,second>

我们先将每个字符串进行排序，然后以该字符串排好序后为基准值，进行存储。

最后我们再将second存储在vector数组中即可~

原码：

代码语言：javascript代码运行次数：0运行复制

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

        vector<vector<string>> ret;
        for(auto& [x,y] : hash)//只需要存储second，也就是y
        {
            ret.push_back(y);
        }
        return ret;
    }
};

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent 删除前往查看数组算法字符串存储数据

本文标签： 算法讲解之哈希表