算法：常见的哈希表算法

文章目录

两数之和
判断是否互为字符重排
存在重复元素
存在重复元素
字母异位词分组

本文总结的是关于哈希表常见的算法

哈希表其实就是一个存储数据的容器，所以其实它本身的算法难度并不高，只是利用哈希表可以对于一些场景进行优化

两数之和

class Solution 
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        // 把数都丢到哈希表中，哈希表的意义是元素及其对应的下标
        unordered_map<int, int> hash;
        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};
    }
};

判断是否互为字符重排

class Solution 
{
public:
    bool CheckPermutation(string s1, string s2) 
    {
        int hash1[26] = {0};

        for(auto e : s1)
            hash1[e - 'a']++;
        for(auto e : s2)
            hash1[e - 'a']--;
        
        for(int i = 0; i < 26; i++)
            if(hash1[i])
                return false;
        
        return true;
    }
};

存在重复元素

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

其实是可以优化的，不需要看出现了几次，这个题只关心有没有的问题，因此使用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;
    }
};

存在重复元素

class Solution
{
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k)
	{
		unordered_map<int, int> hash;
		for (int i = 0; i < nums.size(); i++)
		{
			if (hash.count(nums[i]) && abs(hash[nums[i]] - i) <= k)
			{
				return true;
			}
			else
			{
				hash[nums[i]] = i;
			}
		}
		return false;
	}
};

字母异位词分组

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_back(s);
        }

        // 再取出来
        vector<vector<string>> res;
        for(auto& [x, y] : hash)
        {
            res.push_back(y);
        }

        return res;
    }
};