哈希表基础知识

哈希表是一种数据结构，也叫散列表。哈希表中存储的是键值对，即(key，value)，根据key直接查找到对应value，也能快速查找key是否在哈希表中，时间复杂度是O(1)。理解：可以把数组看作是哈希表，把数组下标index看作是key，对应下标中存储的是value，通过key查找元素的时候，就像是通过下标index访问数组，直接定位array[index]。
哈希表查找元素时，将key通过哈希函数（hashfunction）后映射为索引，通过该索引找到对应存储的value。

242. 有效的字母异位词

242. 有效的字母异位词
题目描述：【其实我没懂为什么这道题会跟哈希表扯上关系】
理解题意：重点是“什么是字母异位词？”——实际上就是两个单词（字符串）中的字母及其出现的次数都一样，但是出现的顺序不一样。
理解题意后，解题思路就很清晰了，分别遍历s和t，统计其中出现的各个字符及其次数，最后对比这些字符及次数是否完全相等。因为题目中提到都是小写字母，因此用一个长度为26（只有26个小写英文字母），初始化全为0的数组count来记录字符串中各字母出现的次数。在遍历s的时候，对count[s[i]-‘a’]++，表示s中出现的各个字母及其次数；在遍历t的时候，对count[t[i]-‘a’]- -，表示t中出现的各个字母，及能否抵消掉s中该字母出现的次数；【注意直接用s[i]-'a’表示26个字母数组的下标是一种常用操作】最后遍历count数组，如果全为0，表示s和t是字母异位词，如果count中存在不为0的元素，就表示t不完全包括s中需要的字母（或s中不完全包括t中需要的字母）。
代码如下（C++）：

class Solution {
public:bool isAnagram(string s, string t) {//如果两者长度不一样，肯定不是字母异位词if(s.size() != t.size())return false;//统计各字母出现的次数int count[26] = {0};//遍历s，统计其中出现的字母及其次数for(int i = 0; i < s.size(); i++){count[s[i] - 'a']++;}//遍历tfor(int i = 0; i < t.size(); i++){count[t[i] - 'a']--;}for(int i = 0; i < 26; i++){//如果有不为0的元素，表示在该字母上，s和t出现的次数不一样if(count[i] != 0) return false;}return true;}
};

383. 赎金信

383. 赎金信
题目内容：
ransomNote和magazine都由英文小写字母组成。理解题意，实际和上一题，字母异位词差不多，只是在字母异位词中，两个字符串中出现的字母及其次数必须完全一样，在这道题中，用magazine来组成ransomNote【提到magazine中每个字符只能在ransomNote中用一次，是比如ransomNote中有2个a，那么magazine中至少得有2个a才能满足要求】，实际上是要求ransomNote中需要的字母在magazine中都存在，并且magazine中这些字母的次数>ransomNote中出现的次数。
实现过程同样是用count[26]数组来记录出现字母及其次数。先遍历ransomNote，对count[ransomNote[i]-‘a’]- -，表示ransomNote对该字母的需求量；再遍历magazine，对count[magazine[i]-‘a’]++，表示magazine对该字母的提供量；最后如果count中存在<0的元素，说明ransomNote中该字母的需求，magazine不能满足，不能满足题意，返回false。【相反>=0，都是能够满足的】
代码实现（C++）：

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {//如果magazine中总的字符数小于ransomNote，直接返回falseif(magazine.size() < ransomNote.size())return false;int count[26] = {0};//统计ransomNote中各字母的需求量for(int i = 0; i < ransomNote.size(); i++){count[ransomNote[i]-'a']--;}//统计magazine中各字母的提供量for(int i = 0; i < magazine.size(); i++){count[magazine[i]-'a']++;}for(int i = 0; i < 26; i++){//如果有<0的说明magazine中该字母的提供量不能满足ransomNote中的需求量if(count[i] < 0)return false;}return true;}
};

49. 字母异位词分组

49. 字母异位词分组
题目内容：
题目的关键点：①如何判断是字母异位词？方法Ⅰ. 字母异位词中出现的字母及其次数完全相同；方法Ⅱ. 字母异位词将字符串按照字母升序排序后是一样的；②如何对字母异位词分组？方法：哈希表，一组字母异位词key相同，字符串存到value中（很多个字符串怎么存，value用数组，比如vector）； ③如何构造哈希表？ 按照问题①的解决方案（两种对应最终的两种办法），将字符串变成键key，如果是字母异位词那么key是一样的，存到对应的value数组中，即可实现分组。
本题以及哈希表相关题目最最最关键的是，找到是要对什么构造哈希表，什么是key，什么是value。
两种代码分别如下（C++）：

class Solution {
public://方法Ⅰ，把字符串按照字母升序排序得到键key，构造哈希表vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> ans_map; //注意key对应的value是字母异位词构成的vectorvector<vector<string>> ans;//遍历每一个字符串for(string& str_i : strs){string key = str_i;//使用字符串排序后的结果作为keysort(key.begin(), key.end());//将字符串加入到对应的key的value vactor中ans_map[key].emplace_back(str_i);}//取哈希表每个key对应的value（字母异位词分组）for(auto& ans_i : ans_map){ans.emplace_back(ans_i.second);}return ans;}
};class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> ans_map;vector<vector<string>> ans;//方法Ⅱ，把字符串中各个字母出现的次数构成key【比如aabccc，key是"213000……000"】for(string& str_i : strs){string key = string(26, '0');for(auto char_i : str_i)key[char_i-'a']++;//将字符串加入到对应的key的value vector中ans_map[key].emplace_back(str_i);}for(auto& ans_i : ans_map){ans.emplace_back(ans_i.second);}return ans;}
};

438. 找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词
题目内容：【我不知道为什么一定要扯上滑动窗口，这道题不就是遍历s中所有和p长度一样的子串并判断嘛？？？】

理解题意，同样是判断字母异位词；遍历s中所有长度为p.len的子串，然后判断是不是p的字母异位词。怎么遍历子串呢？有一个start一个end，start=0，然后依次移动，end也是；子串移动的过程中，子串的字母及次数数组，对start的- -，对end的++。
代码如下（C++）：

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;int s_len = s.size(), p_len = p.size();//如果s比p短，直接返回空结果if(s_len < p_len) return ans; //统计子串和p中字母及其次数        vector<int> subCount(26,0), pCount(26,0);for(int i = 0; i < p_len; i++){subCount[s[i]-'a']++;pCount[p[i]-'a']++;}//对于第一个子串，先判断if(pCount == subCount)   ans.emplace_back(0);for(int start = 0; start < s_len - p_len; start++ ){//移动到下一个子串            subCount[s[start] - 'a']--; //start对应字母次数--subCount[s[start + p_len] - 'a']++;  //end对应字母次数++（没有用额外的变量end表示，直接用start+p_len//判断新子串和p是否是字母异位词if(subCount == pCount){ans.emplace_back(start + 1);}         }return ans;}
};