【算法专题十】哈希表

0.哈希表简介

1. 两数之和

1.1 题目

题目链接

1.2 思路

1.3 代码

// 法1.1 
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for(int i = 0; i < n - 1; i++){for(int j = i + 1; j < n; j++){if(nums[i] + nums[j] == target) return {i, j};}}return {};}
};

// 法1.2 
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(nums[i] + nums[j] == target) return {i, j};}}return {};}
};

// 法2
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> idx; // 创建一个空哈希表for(int j = 0; ; j++){auto it = idx.find(target - nums[j]);if(it != idx.end())return {it->second, j};idx[nums[j]] = j;}}
};

// 法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 t = target - nums[i];if(hash.count(t)) return {hash[t], i};hash[nums[i]] = i;}return {};}
};

2.判断是否为字符重排

2.1 题目

题目链接

2.2 思路

2.3 代码

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

3. leetcode.217.存在重复元素

3.1 题目

题目链接

3.2 思路

这个题思路跟上一个题的思路有点像，使用哈希表，从前往后遍历，从1开始遍历，判断哈希表中时候有此时的值，没有的话，把现在的值插入哈希表中，然后遍历下一个位置。

3.3 代码

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

4. leetcode.219.存在重复的元素Ⅱ

4.1 题目

题目链接

4.2 思路

4.3 代码

// 法一 两层循环遍历
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {for(int i = 0; i < nums.size(); i++){for(int j = i + 1; j <= i + k && j < nums.size(); j++){if(nums[i] == nums[j])return true;}}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])){if(i - hash[nums[i]] <= k) return true;}  hash[nums[i]] = i;}return false;}
};

5. leetcode.49.字母异位词分组

5.1 题目

题目链接

5.2 思路

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