好大夫在线个人网站王建设肇庆企业做网站
目录
哈希表总结
leetcode题目
一、两数之和
二、判定是否互为字符重排
三、存在重复元素
四、存在重复元素 II
五、字母异位词分组
六、在长度2N的数组中找出重复N次的元素
七、两个数组的交集
八、两个数组的交集 II
九、两句话中的不常见单词
哈希表总结
1.存储数据的容器
2.需要快速查找数据时，用哈希表
3.当题目中给定的字符串或者数组只包含小写字母或数据范围是0~100/1000等等时，可以用数组模拟哈希表
4.当数据范围是负数到正数时，不建议用数组模拟哈希表，因为还要加一个数转化之后进行映射，建议直接使用STL容器
leetcode题目
一、两数之和
1. 两数之和 - 力扣（LeetCode）
https://leetcode.cn/problems/two-sum/1.题目解析
给定数组与target, 返回和为target的两个元素下标
2.算法分析
解法一: 暴力枚举
策略一: 先固定一个数，然后依次与该数之后的数相加
策略二: 先固定一个数，然后依次与该数之前的数相加
解法二: 使用哈希表优化
暴力解法之所以慢，以策略二为例, 是因为枚举到nums[i]时，要在这个位置之前都遍历一下，看哪个数字等于target-nums[i], 所以如果我们枚举到nums[i]时，前面的数字都被扔进了哈希表中，我们就可以以O(1)的时间复杂度找到结果~
注意：如果是用哈希表暴力枚举策略一，最好是倒着遍历~
3.算法代码
暴力枚举策略一:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i < nums.size(); i++){for(int j = i + 1; j < nums.size(); j++){if(nums[i] + nums[j] == target)return {i, j}; }}return {-1, -1};}
};暴力枚举策略二:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 1; i < nums.size(); i++){for(int j = i - 1; j >= 0; j--){if(nums[i] + nums[j] == target)return {i, j}; }}return {-1, -1};}
};哈希表优化策略一:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash; //<nums[i], i>for(int i = nums.size()-1; i >= 0; i--){int x = target - nums[i];if(hash.count(x)) return {hash[x], i};hash[nums[i]] = i;}return {-1, -1}; //照顾编译器}
};哈希表优化策略二:
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 {hash[x], i};hash[nums[i]] = i;}return {-1, -1}; //照顾编译器}
};二、判定是否互为字符重排
面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）https://leetcode.cn/problems/check-permutation-lcci/1.题目解析
给定两个字符串，判断一个字符串是否能够通过重排变成另一个字符串
2.算法分析
如果s1能够重排形成s2, 那么s1每个字符出现的个数和s2对应字符出现的个数是相等的！于是可以使用哈希表，而题目中说字符串只有小写字母，因此用数组模拟哈希表即可。所以解法就是用两个哈希表，然后判断哈希表是否相等即可；
优化1: 只使用一个哈希表统计s1中字符个数，然后遍历第二个字符串，把对应字符在哈希表中的个数--， 如果--之后是负数了，返回false即可
优化2: 两个字符串的长度不相等，直接返回false即可
3.算法代码
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;}
};三、存在重复元素
217. 存在重复元素 - 力扣（LeetCode）https://leetcode.cn/problems/contains-duplicate/1.题目解析
数组中存在重复元素返回true, 不存在重复元素返回false
2.算法分析
使用哈希表解决问题~
3.算法代码
unordered_map:
class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int, int> hash;for(auto& e : nums){hash[e]++;if(hash[e] > 1) return true;}return false;}
};unordered_set:
class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash;for(auto& e : nums){if(hash.count(e)) return true;elsehash.insert(e);}return false;}
};四、存在重复元素 II
219. 存在重复元素 II - 力扣（LeetCode）https://leetcode.cn/problems/contains-duplicate-ii/1.题目解析
判断数组中是否存在两个相同的元素，并且下标的绝对值小于等于k
2.算法分析
从前向后遍历数组，同时将遍历过的元素和下标绑定扔进哈希表，遍历的同时判断是否满足题意即可
小细节：nums = [1 0 2 1 3 1 4], k =2, 当遍历到第2个1时，发现下标i-j=3>k, 不满足题意，此时将1和下标3绑定扔进哈希表覆盖之前的 <1, 0> 是完全可以的, 因为题目求的是 i-j <= k, 因此i和j越近越好，因此我们可以直接覆盖原先的值~
3.算法代码
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++){if(hash.count(nums[i]) && i-hash[nums[i]] <= k)return true;hash[nums[i]] = i;}return false;}
};五、字母异位词分组
49. 字母异位词分组 - 力扣（LeetCode）https://leetcode.cn/problems/group-anagrams/description/1.题目解析
给一个字符串数组，将所有的字母异位词放到一组，返回一个二维数组
2.算法分析
1.判断两个字符串是否是字母异位词(可以用哈希表，但是代码不好写，我们选择直接排序, 排序结果一样，那就互为字母异位词)
2.将相同的字母异位词分组 --- 借助哈希表 <string, string[ ]>, 哈希表第一个位置存储排序后的字符串，第二个存储一个字符串数组；
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){ret.push_back(y);}return ret;}
};六、在长度2N的数组中找出重复N次的元素
961. 在长度 2N 的数组中找出重复 N 次的元素 - 力扣（LeetCode）https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/description/1.题目解析
我们在深剖一下题意，本质就是只有1个数重复出现了，其他数都只出现了一次
2.算法分析
思路一: 遍历数组，将当前元素和出现次数丢进哈希表，当某个数出现次数 == n时，返回该数
思路二: 遍历数组，进循环先判断该数是否已经存在，存在就直接返回，不存在就将该数丢进哈希表
3.算法代码
思路一:
class Solution {
public: int repeatedNTimes(vector<int>& nums) { size_t n = nums.size() / 2;unordered_map<int, int> hash; // [x, count] for(auto& e : nums) { hash[e]++; if(hash[e] == n) return e; } return -1;}
};思路二:
class Solution {
public: int repeatedNTimes(vector<int>& nums) { unordered_map<int, int> hash; // [x, count] for(auto& e : nums) { if(hash[e] == 1) // 只需要检查是否已经存在（即重复了一次） return e; hash[e]++; } return -1;}
};七、两个数组的交集
349. 两个数组的交集 - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-arrays/submissions/
1.题目解析
返回两个数组的交集（输出结果的每个元素要是唯一的）
2.算法分析
将两个数组元素扔进两个 unordered_set 哈希表进行去重，然后遍历其中一个哈希表，看该哈希表中的元素在另一个哈希表中是否存在，存在就插入到结果数组中！
3.算法代码
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> ret;unordered_set<int> hash1;unordered_set<int> hash2;for(auto& e : nums1) //对nums1元素去重hash1.insert(e);for(auto& e : nums2) //对nums2元素去重hash2.insert(e);for(auto& e : hash1)if(hash2.count(e))ret.push_back(e);return ret;}
};八、两个数组的交集 II
350. 两个数组的交集 II - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-arrays-ii/1.题目解析
返回两个数组的交集 (结果中可以有重复元素)
2.算法分析
定义一个哈希表 unordered_map，遍历第一个数组，将 数组元素和出现的个数绑定扔进哈希表, 然后遍历第二个数组，元素在哈希表中出现，就插入到结果数组中，然后将该元素在哈希表中的个数--即可
3.算法代码
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> hash;for(auto& e : nums1)hash[e]++;vector<int> ret;for(auto& e : nums2){if(hash[e]){ret.push_back(e);hash[e]--;}}return ret;}
};九、两句话中的不常见单词
884. 两句话中的不常见单词 - 力扣（LeetCode）https://leetcode.cn/problems/uncommon-words-from-two-sentences/description/
1.题目解析
返回两句话中互相在另一句话中没有出现的所有单词
2.算法分析
可以将两个字符串合在一起，提取出所有的单词同时扔进哈希表统计单词出现的次数，然后遍历一遍哈希表，出现次数为1的单词就是我们要的结果
3.算法代码
class Solution {
public:vector<string> uncommonFromSentences(string s1, string s2) {//1.将所有的单词提取出来vector<string> words;string tmp;string s = s1 + ' ' + s2;unordered_map<string, int> hash;for(size_t i = 0; i <= s.size(); i++){if(s[i] != ' ' && i != s.size())tmp += s[i];else{words.push_back(tmp);hash[tmp]++;tmp.clear();}}//2.从哈希表中提取结果vector<string> ret;for(auto [x, y] : hash)if(y == 1)ret.push_back(x);return ret;}
};十、字符串中的第一个唯一字符
387. 字符串中的第一个唯一字符 - 力扣（LeetCode）https://leetcode.cn/problems/first-unique-character-in-a-string/
1.题目解析
找字符串中第一个只出现一次的字符
2.算法分析
数组模拟哈希表，遍历字符串s，统计出每个字符出现的次数，然后再遍历一遍哈希表，找出出现次数为1的字符，返回下标
3.算法代码
class Solution {
public:int firstUniqChar(string s) {int hash[26] = {0};for(auto& e : s)hash[e-'a']++;for(int i = 0; i < s.size(); i++)if(hash[s[i]-'a'] == 1)return i;return -1;}
};