重练算法（代码随想录版） day6 - 哈希表part1

day5周日休息一天

今日刷题量：8
当前刷题总量：33
Easy: 20
Mid: 12
Hard: 1

Day 6
基础理论
1.哈希表通常用来判断一个元素是否出现在集合里，牺牲空间来换时间。
2.通过哈希函数得到索引，将元素存储在索引对应的位置形成映射
3.若有哈希冲突，多个元素通过哈希函数得到同一个索引，可采取拉链法、线性探测法、再哈希法、平方地址法等解决
4.常用哈希结构：数组、set（集合）、map（映射）
（1）set/multiset，map/multimap底层实现都是红黑树，元素默认升序，查询和增删效率都是O（logn）前后者区别在于元素能否重复
（2）unordered_set、unordered_map底层实现为哈希表，元素无序，查询和增删效率O（1）

练习题目

• 242.有效的字母异位词（easy）：https://leetcode.cn/problems/valid-anagram/description/

• 383.赎金信（easy）：https://leetcode.cn/problems/ransom-note/description/

• 49.字母异位词分组（mid）：https://leetcode.cn/problems/group-anagrams/description/

• 438.找到字符串中所有字母异位词（mid）：https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

• 349. 两个数组的交集（easy）：https://leetcode.cn/problems/intersection-of-two-arrays/description/

• 350.两个数组的交集Ⅱ（easy）：https://leetcode.cn/problems/intersection-of-two-arrays-ii/description/

• 202. 快乐数（easy）：https://leetcode.cn/problems/happy-number/submissions/625510761/
       ps：快乐数此题也可以采用Floyd判圈算法的思想，无需额外空间存储已访问数字，可用来判断循环
• 1. 两数之和（easy）：https://leetcode.cn/problems/two-sum/description/