【LeetCode热题100】哈希表

这篇博客记录了几道哈希表相关的题目，包括两数之和、判定是否互为字符串重排、存在重复元素II、字母异位词分组。

//解法1
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        vector<int> ret;
        for(int i = 1 ; i < nums.size() ; i++)
        {
            for(int j = 0 ; j < i ; j++)
            {
                if(nums[i]+nums[j] == target)
                {
                    ret.emplace_back(i);
                    ret.emplace_back(j);
                    return ret;
                }
            }
        }
        return ret;
        
    }
};
//解法2
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 tmp = target - nums[i];
            if(hash.count(tmp)) return {i,hash[tmp]};
            hash[nums[i]] = i;
        }
        return {-1,-1};
        
    }
};

题目分析：关于这道题，我们有两种思路：

思路1：暴力求解

我们从从头开始固定一个数，然后去前面找是否存在满足要求的数，也是是通过两层循环去遍历。但是这种解法的时间复杂度是O(N2)。

思路2：哈希表

从头开始固定一个数，然去取哈希表中去找是否存在满足要求的数，如果不存在，将其放在哈希表中，然后固定下一个数，再去哈希表中去找是否存在满足要求的数，依次类推。

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;
    }
};

题目分析：本题采用哈希表的方式解决，由于全为小写字母，那么就可以使用数组模拟哈希表。首先，如果两个string长度不相等，那么肯定不符合要求。我们只需要创建一个哈希表即可。先将第一个string的字母挨个放到哈希表中，然后再遍历第二个哈希表，找到相同字母后，对应字母自减，如果减为负数，那么肯定不符合要求，返回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]))
                if(i-hash[nums[i]] <= k) return true;
            hash[nums[i]] = i; 
        }
        return false;
    }
};

题目分析：和I一样，也是使用哈希表，遍历nums，并把遍历过的元素放到哈希表中，判断符不符合要求。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        //1.先将所有字母异位词分组
        unordered_map<string,vector<string>> hash;
        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;
    }
};

题目分析：解决这道题分两步，第一步，先把所有字母异位词分组，使用哈希表这个容器，unordered<string,vector<string>>，键值string存放的是字符串排序完之后的字符串（比如，“eat”排序完之后是“aet”，那么把“aet”放入键值），val放的是对应真实字符串，把字符串数组遍历一遍后，第二步，对得到的哈希表进行遍历，把其val放入vector<vector<string>>中。