?根据代码随想录，记录学习一些算法经验
哈希表（散列表），是根据关键码的值直接访问的数据结构，以数组来解释比较直接，这个关键码就是数组的下标，通过下标直接访问元素，哈希表用来快速判断一个元素是否出现在集合里。数组查找是O(1)操作，
哈希函数是将其他的数据格式转换成不同数值，映射到哈希表上的索引数字，
哈希碰撞两个数据映射到同一个位置，解决方法：拉链法和线性探测法，拉链法就是将冲突的元素存在链表中，注：要选择合适的哈希表大小，线性探测法要保证哈希表的大小大于数据大小，如果碰撞发生找数组上下一个空位置放碰撞的元素，所以注：哈希表大小要大于数据大小，
常见三种哈希结构：
数组，set集合，map映射，
set：有三种set(红黑树，键有序),multiset(红黑树，键有序),unordered_set(哈希表，无序)（不可以更改数值）红黑树的查询和增删效率都是O(log n)，而哈希表都是O(1)，红黑树底层是平衡二叉搜素树，所以要求Key有序，
map:有三种map(红黑树，key有序),multimap(红黑树，key有序),unordered_map(哈希表，key无序),红黑树的查询和增删效率都是O(log n)，而哈希表都是O(1)
用集合来解决哈希问题，首先考虑unordered_set，效率最高，要求集合有序set,如果还要求有重复元素multiset。
map是键值对，是一个key value 的数据结构，对key是有限制，对value没有限制的。
虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。
数值比较小情况下使用数组，数值比较大情况用set，如果有key有值对应用map
哈希法：快速判断一个元素是否在集合里，典型利用空间换时间的方法。
题目描述：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。（说白了就是是否一个字符串是否是由另一个字符串字母组成的）(注：字符串只有小写字母)
示例?1: 输入: s = "anagram", t = "nagaram" 输出: true
思想：因为字符串是小写字母，我们用一个数组来记录每个字符出现的次数即可，这个数组定义长度为26的数组，初始化为0，字符a到z，对s[i]-‘a’下标的元素记录，
class Solution {
public:
bool isAnagram(string s, string t) {
int recod[26]={0};//申请一个数组的哈希表，这个数组大小就是小写字母个数大小，初始化为0
for(int i = 0;i<s.length();i++){//遍历s字符串，将s字符串的每一个字符跟a字符进行做差对应位置进行操作++，记录元素
recod[s[i]-'a']++;
}
for(int j = 0;j<t.length();j++){//遍历T字符串，相反的操作
recod[t[j]-'a']--;
}
for(int i = 0;i<26;i++){//遍历整个数组，如果有不为0说明不是字母异位词
if(recod[i]!=0){
return false;
}
}
return true;//
}
};?时间复杂度为O(n)，空间复杂度为O(1)。
题目描述：给定两个数组，编写一个函数来计算它们的交集，输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]，输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
思想：由于数组的树可能比较大，所以不太适用数组进行操作考虑set哈希结构，由于去重，且不考虑顺序，所以考虑unordered_set哈希表数据结构，
哈希值比较少，且比较分散，跨度比较大的时候不适用数组做哈希表。
其实哈希表的底层是无线存装的数组。
使用unordered_set哈希表进行操作
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());//将nums1数组映射哈希表nums_set中，其实就是将nums1作为哈希表
for(int num : nums2){//从nums2中遍历元素
if(nums_set.find(num) != nums_set.end()){//在哈希表发现这个元素
result_set.insert(num);//放入结果哈希表进行去重，
}
}
return vector<int>(result_set.begin(),result_set.end());//返回结果数组
}
};find()函数返回一个迭代器，指向范围内搜索元素的第一次出现。如果没有找到目标元素，则返回last，即查找范围的结尾。
find()也可以用于vector容器，用于查询指定元素是否存在。还有一个STL函数find()，它位于<algorithm>头文件下，返回一个迭代器，指向范围内搜索元素的第一次出现。
string类的find()函数用于在字符串中查找字符或子串，返回第一个匹配的位置。
find()函数是一个通用的算法，它可以在任何容器中查找指定元素，返回一个迭代器指向第一个匹配的元素。
如果it != v.end()，则说明find()函数找到了目标元素；否则，说明没有找到目标元素。
?使用数组哈希表进行求解
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int>result_set;//结果哈希表
int hash[1005] = {0};//定义数组作为哈希表
for(int num : nums1){//遍历nums1数组，出现的数字哈希表为1
hash[num] = 1;
}
for(int num : nums2){//遍历nums2数组，如果哈希表数字等于1，说明有相同数字
if(hash[num] == 1){//插入结果集
result_set.insert(num);
}
}
return vector<int>(result_set.begin(),result_set.end());//返回结果
}
};两个都为这个时间复杂度和空间复杂度。
?题目描述：
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为? 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
思想：首先求得每一轮的总和，定义一个接口去计算，使用哈希表unordered_set去接收这个每一轮的sum值，如果重复立即返回错，如果sum==1返回正确，否则继续将sum映射到哈希表中，更新每次需要计算的值。
class Solution {
public:
int getSum(int n){//获取每一个位值的平方和
int sum = 0;//定义一个变量接收
while(n != 0){//位数操作
sum += (n%10)*(n%10);//每个位操作进行平方操作
n /= 10;//之后再进行取余
}
return sum;
}
bool isHappy(int n) {
unordered_set<int>result;//定义一个哈希表接收每轮和的值
while(1){
int sum = getSum(n);//得到总和的值
if(sum == 1){//如果和为1返回真
return true;
}
if(result.find(sum) != result.end()){//如果查询这个和发现有一个元素相同，立即返回错
return false;
}else{//没有这个元素就插入哈希表中
result.insert(sum);
}
n = sum;//更新新的N值
}
}
};?暴力解法：可以过但是时间较长，两个循环去完成,时间复杂度是O（n^2）。
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 {};
}
};使用哈希表方法：本题由于需要记录第一个位置的值，需要两个参数，需要判断y存在，也要记录y的下标位置，返回两个下标，所以应该采用map数据结构，是一种键值对的存储结构，key用来保存数值，用value保存数值所在的下标。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;//定义一个map数据结构，存放遍历过元素，map第一个key是元素，第二个是value是下标
for (int i = 0; i < nums.size(); i++) {//
auto iter = map.find(target - nums[i]);//容器的操作，查找，如果找到，返回
if (iter != map.end()) {//找到返回迭代器的第二个参数，也就是下标，和i
return {iter->second, i};//
}
map.insert(pair<int, int>(nums[i], i));//没有找到就存放到哈希表中
}
return {};//返回下标
}
};题目描述：给定四个包含整数的数组列表?A , B , C , D ,计算有多少个元组 (i, j, k, l)?，使得?A[i] + B[j] + C[k] + D[l] = 0。
输入:
输出：2
哈希表方法：将A，B两个数组看成一个整体吧，先将两个数组进行和运算，之后和两数之和一样的，进行一个判断操作。
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值出现的次数
for(int a : nums1){//遍历A，B两个数组，统计两个数组元素之和以及元素和出现的次数
for(int b : nums2){
umap[a+b]++;
}
}
int count = 0;//a+b+c+d=0出现的次数
for(int c : nums3){//遍历C,D两个数组，如果-（c+d）在Umap中出现的次数，和两数之和的逻辑一样
for(int d : nums4){
if(umap.find(0 - (c+d)) != umap.end()){
count+=umap[0 - (c+d)];//次数
}
}
}
return count;
}
};题目描述：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
暴力实现：双循环实现
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
for (int i = 0; i < magazine.length(); i++) {
for (int j = 0; j < ransomNote.length(); j++) {
// 在ransomNote中找到和magazine相同的字符
if (magazine[i] == ransomNote[j]) {
ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
break;
}
}
}
// 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
if (ransomNote.length() == 0) {
return true;
}
return false;
}
};题目解析：不可重复使用，且小写字母，所以采用数组完成。
哈希表实现：代码逻辑和字母异位词相似，使用数组作为哈希表来完成查找操作即可实现。
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {//代码逻辑可以参考字母异位词
int recod[26]={0};
for(int i = 0;i<ransomNote.size();i++){
recod[ransomNote[i] - 'a']++;
}
for(int i = 0;i<magazine.size();i++){
recod[magazine[i] - 'a']--;
}
for(int i = 0;i < 26;i++){
if(recod[i]>0){//说明ransomnote中有字母在magazine中没有
return false;
}
}
return true;
}
};题目描述：给你一个包含 n 个整数的数组?nums，判断?nums?中是否存在三个元素 a，b，c ，使得?a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：?答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
哈希表解法：需要考虑去重问题，主要是对b去重这部分比较难考虑
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[j], c = -(a + b)
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重
continue;
}
unordered_set<int> set;
for (int j = i + 1; j < nums.size(); j++) {
if (j > i + 2
&& nums[j] == nums[j-1]
&& nums[j-1] == nums[j-2]) { // 三元组元素b去重
continue;
}
int c = 0 - (nums[i] + nums[j]);
if (set.find(c) != set.end()) {
result.push_back({nums[i], nums[j], c});
set.erase(c);// 三元组元素c去重
} else {
set.insert(nums[j]);
}
}
}
return result;
}
};双指针方法，首先将数组进行排序，对i去重，之后左右指针移动找到符合的值，之后在去重左右指针，之后再进行后面的循环语句。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {//重点在去重操作
vector<vector<int>> result;//创建一个结果集
sort(nums.begin(), nums.end());//对数组进行排序
for (int i = 0; i < nums.size(); i++) {//定义一个指针做外层遍历
if (nums[i] > 0) {//排序按照从小到大排序，如果第一个元素大于零后面无论加什么都大于0，退出
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) {//去重i，要跟前一个i进行对比如果相等就去重，保证不能出现下标负数
continue;
}
int left = i + 1;//定义内循环左右指针从i+1,和末尾开始
int right = nums.size() - 1;
while (right > left) {//定义循环条件
if (nums[i] + nums[left] + nums[right] > 0) {//假设值整体大于0右指针向左移动
right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {//小于0左指针向右移动
left++;
} else {//找到符合目标的数组，插入到结果集中，
result.push_back(
vector<int>{nums[i], nums[left], nums[right]});
while (right > left && nums[right] == nums[right - 1]) {//去重对右指针，和i去重一个思想
right--;
}
while (right > left && nums[left] == nums[left + 1]) {//去重对左指针
left++;
}
right--;//将左右指针向前移动
left++;
}
}
}
return result;
}
};这里面对i去重有一个小细节，注：不能是nums[i]==nums[i+1]，这个不是对I进行去重，而是将i与left进行对比。?还有对b,.c进行去重时，应该是在找到一个三元组之后再去去重。
题目描述：
给定一个包含?n 个整数的数组?nums?和一个目标值?target，判断?nums?中是否存在四个元素 a，b，c?和 d?，使得?a + b + c + d?的值与?target?相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
双指针解法：和三数之和一个套路，在三数之和在套一层循环即可，这次两个循环，确定nums[i]+nums[k]的值，再定义两个指针左右两个指针查找四个数和为target的操作，双指针方法就是将原来n^3的操作降为n^2的操作。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>>result;
sort(nums.begin(),nums.end());
for(int i = 0;i < nums.size(); i++){//第一层循环
if(i > 0 && nums[i] == nums[i-1]){//注意去重I
continue;
}
for(int k = i+1;k < nums.size();k++){//第二层循环
if(k > i+1 && nums[k] == nums[k-1]){//注意去重k
continue;
}
int left = k+1;//和三数之和做法一样，双指针操作
int right = nums.size()-1;
while(right > left){
if(nums[k] + (long)nums[i] + nums[left] + nums[right]> target){//注意强转
right--;
}else if(nums[k] + (long)nums[i] + nums[left] + nums[right]< target){
left++;
}else{
result.push_back(vector<int>{nums[i],nums[k],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;
}
};哈希表的理论：哈希表就是查询一个元素比较快，是否出现在一个集合里，也就是根据下标或者key来查询，理解哈希碰撞，掌握三种哈希表的形式数组，set,map数据结构，知道每个数据结构分类的每个特性，以及底层实现，和什么时候使用
有效字母异位词：在目标数据范围比较小，且数量比较大，可以优先使用数组进行哈希操作，根据小写字母个数创建哈希表来进行映射，
两个数组的交集：由于数组中存放是整数，范围比较大，且跨度较大，所以采用unorder_set哈希表进行哈希操作，无序和不重复，利用find函数来查找，！=end()则代表找到元素。
快乐数：含义是一个数的每一位的平方之和得到新的数据，如果最后得到1则是，如果出现重复则不是，转换为判断是否 出现重复数字，采用unordered_set数组接收每一次的数据然后判断是否出现重复，主要在求解每一次的和，之后思想和两个数组交集想法相同。
两数之和：这个需要返回两个数组的下标，而且不能进行排序操作，所以采用的是unordered_map哈希表进行操作，因为需要记录每个元素的下标，采用键值对的方式来记录，一定要记住key和value是什么
四数相加：这个是给定四个数组，来进行操作，同样需要下标和值，所以定义unordered_map进行操作，其实思想和字母异位词的想法差不多，每次记录两个数组的和，之后再去找目标值剩余两个数组。
赎金信：思想和字母异位词一样，数组解决了
三数之和：哈希表可做但是去重操作比较麻烦，采用双指针方法，首先需要排序，来一个for循环，需要对这for的元素进行去重操作，在定义两个指针进行操作，如果不满足条件对应的进行指针操作即可，直到满足条件将数组插入结果集，再进行指针的去重操作。
四数之和：其实和三数之和思想一样，就是需要定义两个循环去接受，使用双指针，依然进行去重个操作。
这里面三数之和很经典值得多次思考，还有两数之和，都很棒值得仔细回味。