每日算法-哈希表（两数之和、）

一.两数之和

1.1题目描述

1.2题解思路

利用哈希表，先判断hash表中有无target-nums[i]的值，再将nums[i]放入到hash表中

1.3题解代码

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> ret;unordered_map<int,int> hash;//nums[i] 数组下标for(int i = 0; i < nums.size(); i++){//判断i之前的数据有无target-nums[i]的值int key = target-nums[i];if(hash.count(key)){//找到了ret.push_back((hash[key]));ret.push_back(i);break;}//将nums[i]放入到hash表中hash[nums[i]] = i;}return ret;}
};

二.判断是否互为字符重排

2.1题目描述

2.2题解思路

定义两个hash表，hash1记录第一个字符串，hash2记录第二个字符串，判断hash1和hash2是否相等即可。

优化：只定义一个hash表，记录第一个字符串时，执行++操作，记录第二个字符串时，执行--操作，最后遍历一遍hash表，看是否为0

2.3题解代码

class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size() != s2.size()) return false;//数组下标char 数组存的数据intint hash[26];for(auto &e : s1){++hash[e-97];}for(auto &e : s2){--hash[e-97];}for(auto &e : hash){if(e != 0) return false;}return true;}
};

三.存在重复元素II

3.1题目描述

3.2题解思路

利用哈希表，先判断hash表中有无nums[i]，若有则继续判断其下标之差是否<=k，再将nums[i]放入到hash表中

3.3题解代码

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,int> hash;//nums[i] i//遍历一遍nums，将nums中的数据放入到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;}
};

四.字母异位词分组

4.1题目描述

4.2题解思路

定义一个hash表,key值存排序后的string，value存原始的string列表。

遍历strs，将数据存储到hash表中，最后再遍历hash表，value中存储的值就是答案

4.3题解代码

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>> hash;//排序之后的string，原始的string列表for(int i = 0; i < strs.size(); i++){//首先进行排序string tmp = strs[i];sort(strs[i].begin(),strs[i].end());//把数据放入到hash表中hash[strs[i]].push_back(tmp);}vector<vector<string>> ret;for(auto& kv: hash){ret.push_back(kv.second);}return ret;}
};