1，定义
哈希表（英文名字为Hash table，又称散列表）
哈希表是根据关键码的值而直接进行访问的数据结构。
其实数组就是一张哈希表，哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。
2，哈希表解决的问题
一般哈希表都是用来快速判断一个元素是否出现集合里。
例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1) 就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。
3，哈希碰撞
如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞(Collision)。
有可能两个不同的原始值在经过哈希运算后得到同样的结果，这样就是哈希碰撞。
例如小李和小王都映射到了索引下表 1的位置，这一现象叫做哈希碰撞。
4，哈希碰撞解决方法
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
拉链法：
刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了。
拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
线性探测法：
使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。
5，常见的三种哈希结构
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
数组
set （集合）
map(映射)
6，leetCode哈希表题目
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for (int i = 0; i < s.size(); i++) {
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
record[s[i] - 'a']++;
}
for (int i = 0; i < t.size(); i++) {
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] != 0) {
// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
// record数组所有元素都为零0，说明字符串s和t是字母异位词
return true;
}
};
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26] = {0};
for (int i = 0; i < ransomNote.size(); i++) {
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
record[ransomNote[i] - 'a']++;
}
for (int i = 0; i < magazine.size(); i++) {
record[magazine[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] > 0) {
// record数组如果有的元素大于零0，说明字符串ransomNote中有某个字符的个数是magazine中多的。
return false;
}
}
// record数组所有元素都为零0，说明字符串s和t是字母异位词
return true;
}
};
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hashmap;
for(auto s : strs){//遍历strs中的每一个字符串
string temp = s;
sort(temp.begin(), temp.end());//字母相同的字符串排完序之后结果相同
hashmap[temp].push_back(s);
}
int len = hashmap.size();
vector<vector<string>> ans(len);//存放结果
int index = 0;
for(auto i : hashmap){
ans[index] = i.second;
++ index;
}
return ans;
}
};
给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。
示例 1：
输入：words = ["bella","label","roller"]
输出：["e","l","l"]
示例 2：
输入：words = ["cool","lock","cook"]
输出：["c","o"]
class Solution {
public:
vector<string> commonChars(vector<string>& words) {
vector<string> result;
if (words.size() == 0) return result;
int hash[26] = {0}; // 用来统计所有字符串里字符出现的最小频率
for (int i = 0; i < words[0].size(); i++) { // 用第一个字符串给hash初始化
hash[words[0][i] - 'a']++;
}
int hashOtherStr[26] = {0}; // 统计除第一个字符串外字符的出现频率
for (int i = 1; i < words.size(); i++) {
memset(hashOtherStr, 0, 26 * sizeof(int));
for (int j = 0; j < words[i].size(); j++) {
hashOtherStr[words[i][j] - 'a']++;
}
// 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
for (int k = 0; k < 26; k++) {
hash[k] = min(hash[k], hashOtherStr[k]);
}
}
// 将hash统计的字符次数，转成输出形式
for (int i = 0; i < 26; i++) {
while (hash[i] != 0) { // 注意这里是while，多个重复的字符
string s(1, i + 'a'); // char -> string
result.push_back(s);
hash[i]--;
}
}
return result;
}
};
给定两个数组，编写一个函数来计算它们的交集。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set; // 存放结果
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2) {
// 发现nums2的元素 在nums_set里又出现过
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
第202题. 快乐数 (https://leetcode-cn.com/problems/happy-number/)
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> set;
while(1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
// 取数值各个位上的单数之和
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
};
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < nums.size(); i++) {
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
第454题.四数相加II (https://leetcode-cn.com/problems/4sum-ii/)
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
for (int a : nums1) {
for (int b : nums2) {
umap[a + b]++;
}
}
int count = 0; // 统计a+b+c+d = 0 出现的次数
// 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
for (int c : nums3) {
for (int d : nums4) {
if (umap.find(0 - (c + d)) != umap.end()) {
count += umap[0 - (c + d)];
}
}
}
return count;
}
};
第15题. 三数之和 (https://leetcode-cn.com/problems/3sum/)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
// 错误去重方法，将会漏掉-1,-1,2 这种情况
/*
if (nums[i] == nums[i + 1]) {
continue;
}
*/
// 正确去重方法
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
/*
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
*/
if (nums[i] + nums[left] + nums[right] > 0) {
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
left++;
} else {
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个三元组之后
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
return result;
}
};
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：
0 <= a, b, c, d < n-
a、b、c和d互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
//这种剪枝是错误的，这道题目target 是任意值
// if (nums[k] > target) {
// return result;
// }
// 去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 正确去重方法
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
if (nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
} else if (nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个四元组之后
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
};
WC136 最长无重复子数组 (牛客网)
给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
class Solution {
public:
/**
*
* @param arr int整型vector the array
* @return int整型
*/
int maxLength(vector<int>& arr) {
// write code here
unordered_map<int , int> mymap;
int i = 0 , Max = INT_MIN;
while(i<arr.size())
{
mymap.clear();
mymap[arr[i]] = i;
int j = i+1;
while(j<arr.size())
{
if(mymap.count(arr[j])==0)//返回匹配特定键的元素数量
{
mymap[arr[j]] = j;
}
else
{
i = mymap.at(arr[j]);//访问指定键值的元素
break;
}
j++;
}
i++;
int temp = mymap.size();
Max = max(Max , temp);
}
return Max;
}
};
参考：代码随想录公众号
链接：https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247489134&idx=2&sn=a0b218da8ffd81a7fe0d3ec6a52e00c9&scene=21#wechat_redirect
题目来源：力扣（LeetCode）
