【算法】哈希表
引言
哈希表，其作用在于快速查找特定的值，从而优化时间复杂度，但会增加空间复杂度，典型以空间换时间。在做题的过程中，可以用数组模拟（数据范围小且数据为正），也可以用容器实现。
一、两数之和
思路：
- 暴力解法：我们每次先固定一个数，再查找该数之前的所有数（这里的思路和普通暴力略有不同）
- 利用哈希表优化：每次遍历完一个数，将其存入哈希表，再次查找时就不用依次往前遍历
为什么之前的暴力策略不好用了呢？因为按照之前的暴力策略，要事先将所有的数都存入哈希表中，再在哈希表中进行查找。同时，因为有可能查找到自身元素，所以还要额外判断排除这种情况。
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 n = target - nums[i];
if(hash.count(n)) return {hash[n], i};
hash[nums[i]] = i;
}
return {};
}
};
二、判断字符重排
思路：
- 先判断两个字符串长度是否相等，若不相等则肯定不能重排
- 利用哈希表，统计每个字母出现的个数
- 遍历s1，增加字符个数，遍历s2，减少字符个数，当字符个数为负数，则不能重排（同时这样可以只使用一个哈希表）
- 若最后没有字符个数为负数，则代表也没有字符个数为正（因为两个字符串长度相等，拥有的字符数相等），则代表对应的字符数相等
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;
}
};
三、存在重复元素
思路：
- 和两数之和的策略相似
- 先在哈希表中查找是否存在该数
- 再将该数存入哈希表
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_set<int> hash;
for(auto x : nums)
{
if(hash.count(x)) return true;
hash.insert(x);
}
return false;
}
};
四、存在重复元素 ||
思路：
- 与存在重复元素思路相似，只不过增加了一个条件
- 所以哈希表要多存储元素的下标
- 先判断哈希表内是否存在符合条件的值，再将该值和下标存入哈希表
- 值得注意的是，本题要求的是距离<=k，所以存入哈希表可以大胆覆盖距离更远的相同元素，但是如果改成>k的话，这种策略就失效了
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int, int> hash;//<nums[i], i>
for(int i=0; i<nums.size(); i++)
{
int x = nums[i];
if(hash.count(x) && i - hash[x] <= k) return true;
hash[x] = i;
}
return false;
}
};
五、字母异位词分组
思路：
- 通过本题，我们可以了解高级语言中容器和泛型编程的强大之处
- 创建哈希表，存储字符串和字符串数组
- 对于每一个单词，我们先对其排序，这样所有的异位词都对应同一个字符串
- 再将排序后的字符串，作为哈希表的键值，其对应的字符串数组添加原字符串
- 最后，再遍历一遍哈希表，把字符串数组依次添加到ret中
class Solution
{
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string, vector<string>> hash;
for(auto& str : strs)
{
string s = str;
sort(s.begin(), s.end());
hash[s].push_back(str);
}
vector<vector<string>> ret;
for(auto& kv : hash) ret.push_back(kv.second);
return ret;
}
};
