LeetCode刷题 -- 哈希表

两数之和

题目链接

题目解析

算法原理

法一：暴力枚举，固定第一个数，从第二个数开始遍历找两数之和为target,从固定的数往后遍历
法二：暴力枚举，固定第一个数，从第一个数遍历到固定的数

法三：从法二的基础上，加入一个哈希表，只要前面的数和固定的数相加不等于target就丢入哈希表中，相等就返回两个数的下标

法四：在法一的基础上，加入一个哈希表，先把所有的数丢入哈希表中，在判断固定的数和表中的数相加是否为target,但是要特判同一个数相加为target
比如[1,3,4,5] target = 8 固定的数是4,哈希表中的数也是4，这样要判断 nums[i] == x&&hash[nums[i]] != i ,x = target - nums[i]

代码

class Solution 
{
public:vector<int> twoSum(vector<int>& nums, int target) {// vector<int> ret;// int n = nums.size();// for(int i = 0;i < n;++i)// {//     for(int j = i-1;j >= 0;j--)//     {//        if(nums[i] + nums[j] == target) //        {//         ret.push_back(i);//         ret.push_back(j);//         break;//        }//     }//     if(ret.size() == 2) break;// }// return ret;unordered_map<int,int> hash;// 存储元素的值和下标int n = nums.size();for(int i = 0;i < n;++i){int x = target - nums[i];if(hash.count(x)) return {hash[x],i};// hash.count(x) 是在哈希表中找xelse hash[nums[i]] = i;}return {-1,-1};}
};

面试题 01.02. 判定是否互为字符重排

题目链接

题目解析

s1字符串重排后可以得到s2字符串

算法原理

法一：只用一个数组模拟哈希表，先把字符串1丢入哈希表中，再遍历字符串2，如果字符串2中存在字符串1中的字符，哈希表就减减，如果哈希中的值小于0则为假

法二：用两个数组模拟哈希表，先把字符串1中字符丢入哈希表中，再把字符串2丢入第二个哈希表中，再遍历26个字符判断对应字符是否存在

代码

class Solution 
{
public:bool CheckPermutation(string s1, string s2) {if(s1.size() != s2.size()) return false;int hash[26] = {0};for(auto ch : s1) hash[ch - 'a']++;for(auto ch : s2) {hash[ch - 'a']--;if(hash[ch - 'a'] < 0) return false;}return true;// int hash1[128] = {0}; // s1// int hash2[128] = {0}; // s2// for(int i = 0;i < s1.size();++i)// hash1[s1[i]]++;// for(int i = 0;i < s2.size();++i)// hash2[s2[i]]++;// for(int i = 97;i < 128;++i)// {//     if(hash1[i] != hash2[i]) return false;// }// return true;}
};

存在重复元素

题目链接

题目解析

算法原理

这题和两数之和的解法是一样的
只需要从前往后遍历，把前面的数都加入哈希表中，固定到某个数时，诺某个数出现了第二次就返回true，否则返回false

代码

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

存在重复元素II

题目链接

题目解析

满足两个条件即可返回true,否则返回false

算法原理

只要注意一个细节即可，前面的数对可以被覆盖（hash[nums[i]] = i），因为找i - j <= k,保证下标离得近

代码

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

字母异位词分组

题目链接

题目解析

把字符串按ASCII码排序后的一样的分为一组
返回这样的二维数组

算法原理

1. 先排序再分组(使用哈希表<string,string[]>)
   第一个存字符串，第二个存字符串数组
2. 排好序的下标是一样的因此可以让tmp存下标（存排好序的下标），再把s加入到哈希表中（s保存的是排序前的字符串）
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){// y -> vector<string>// ret的每一行也是vector<string>ret.push_back(y);}return ret;}
};