代码随想录 Day6 哈希表 哈希表理论基础， 242.有效的字母异位词， 349. 两个数组的交集，202. 快乐数，1. 两数之和

yi�� 哈希表理论基础

哈希表是采用了牺牲空间换取时间，因为需要存储额外的数据。

需要快速判断一个元素是否出现在一个 数组中的时候就需要哈希法。

er  242.有效的字母异位词

本题一开始想到的是使用map，感觉是字母和数字的组合

class Solution {public:    bool isAnagram(string s, string t) {        int record[26] = {0};        for (int i = 0; i  
问题： 
 
1. 注意给'a'穿衣服
 
2.想到其实这样一种思路就已经用到了哈希表
 
er  349.两个数组的交集
 
本题一开始还是想要用1000个元素的数组哈希借了上一题的思路，也可以ac
 
（1）数组
 
vector intersection(vector& nums1, vector& nums2) {        unordered_set result;        int record[1010];        for(int i = 0; i  
（2）全set  如果题目是以前的样子也就是数据的数量是不限的
 
class Solution {public:    vector intersection(vector& nums1, vector& nums2) {        unordered_set result_set; // 存放结果，之所以用set是为了给结果集去重        unordered_set 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(result_set.begin(), result_set.end());    }};
 
 问题：
 
1. string 和vector中存储数据的或者字母的多少都可以通过.size()获取
 
2. unorder_set 可以直接帮助去重，这个地方也用到它的底层原理，unordered_set的底层是哈希表所以说这样在查找一个元素的时候O(1)
 
3.for(int num : nums2)表示遍历nums2中的每一个元素，end()指向最后一个有效的元素的下一个位置
 
san 202.快乐数
 
本题一个主要的难点也是在于如果不能够找到的话就传回不行，所以说需要判断是否曾经出现过相同的值的元素，这个地方使用unordered_set，如果说后来又出现了原来的元素的话采用find方法检查
 
(1)代码随想录的
 
class Solution {public:    // 取数值各个位上的单数之和    int getSum(int n) {        int sum = 0;        while (n) {            sum += (n % 10) * (n % 10);            n /= 10;        }        return sum;    }    bool isHappy(int n) {        unordered_set 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;        }    }};
 
（2）自己思路
 
bool isHappy(int n) {        multiset record;        unordered_set result;        while(1){            result.insert(n);            while(n != 0){                record.insert(n%10);                n /= 10;            }                    while(!record.empty()){                int num = *record.begin();                n += num * num;                record.erase(record.begin());            }            if(n == 1) return true;            if(result.find(n) != result.end()){                return false;            }        }    }
 
问题：
 
1.  主要是注意循环的条件设置，每个条件式位置的设置可能出现错误
 
例如while(1),result.insert(x)不能设置在while循环中
 
si  1.两数之和
 
class Solution {public:    vector twoSum(vector& nums, int target) {        std::unordered_map  map;        for(int i = 0; i second, i};            }            // 如果没找到匹配对，就把访问过的元素和下标加入到map中            map.insert(pair(nums[i], i));         }        return {};    }};
 
问题：
 
1. 算法思路有难度尤其是对于map并不熟悉的时候，是将访问过的元素放入到map，后续遍历的时候不断向前去比对从集合中查找有没有符合的元素即哈希法。
 
哈希法中有vector，set，map，因为我们需要保存元素值和下标值所以采用map，因为我们需要检查map中有没有存在的相应的元素值即key代表元素值。
 
在map中还有三种存储形式，分别是map，multimap，unordered_map，因为unordered_map的底层实现是哈希表所以说查找的效率更高。
 
2. map的书写要求：
 
类型用auto，因为是迭代器。
 
return {1,2};可以这样写
 
unordered_map map  其中的map也可以作为名称，如果担心可以不用这个
 
map插入元素时：map.insert(pair( x, y));
 
return {} 明明说一定会有返回值，但力扣还得要有一个这个
 
基础知识：
 
1.不适合使用数组的情况：数据量很大时，数据很分散(0,1,1000000)
 
这个时候考虑使用set和map
 
2.set系列也分为set，unorder_set,mult_set。
 
三者都不能修改元素的值，理解毕竟红黑树和哈希表，可以进行增删。
 
set和multiset的底层实现都是红黑树，要求数据是有序的，然后一个可以数据是重复的一个不能重复。unorder_set的底层实现是哈希表，所以说在查找元素和增删的时候效率都是非常高的。
 
3. 注意unordered_set转vector的写法:
 
另存时只是作为return，不需要名称vector(result.begin(),result.end());
 
另存时，需要名称last：vector last(result.begin(),result.end())
 
4.set的元素输入的方式是.insert(x)，vector的元素输入的方式是.push_back(x)
 
5.set也是有begin(),end()。set通过insert放入元素，通过erase取出元素
 
6.set中*record.begin()表示迭代器指向的元素，vector中同样如此。