当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
202. 快乐数
编写一个算法来判断一个数
n是不是快乐数。「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果
n是 快乐数 就返回true；不是，则返回false。示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1示例 2：
输入：n = 2 输出：false提示：
1 <= n <= 231 - 1
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现。
当我们遇到了要快速判断一个元素是否出现集合里的时候，考虑哈希法。
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
判断sum是否重复出现就可以使用unordered_set。
class Solution {
public:int getSum(int n){int sum=0;while(n){sum+=pow((n%10),2);n=n/10; // 9/10 = 0 ; 9%10 = 9;}return sum;}bool isHappy(int n) {//无限循环 但始终变不到 1---我们要判断重复 一旦有重复就return falseunordered_set<int> result;while(1) {int sum = getSum(n);if (sum == 1) {return true;}// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return falseif (result.find(sum) != result.end()) {//set.find()没有返回末尾 即中间有相同return false;} else {result.insert(sum);}n = sum;}}
};1. 两数之和
难度简单15556
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
C++ map用法总结（整理）_sevencheng798的博客-CSDN博客_mapc++用法
C++中map，有三种类型：
| 映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(log n) | O(log n) |
| std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
map:
不仅要知道元素有没有遍历过，还有知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。
这道题目中并不需要key有序，选择std::unordered_map 效率更高！
数组和set的局限性：
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
这道题目中并不需要key有序，选择std::unordered_map 效率更高。
map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）。
这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。
判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。
所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下表}。
在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。
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++) {// 遍历当前元素，并在map中寻找是否有匹配的keyauto iter = map.find(target - nums[i]); if(iter != map.end()) {return {iter->second, i};}// 如果没找到匹配对，就把访问过的元素和下标加入到map中map.insert(pair<int, int>(nums[i], i)); }return {};}
};iterator->second意思：
std::map<X, Y>实际储存了一串std::pair<const X, Y>std::map<std::string, int> m = /* fill it */; auto it = m.begin();这里，如果你用
*it，那么你将得到map第一个元素的std::pair：现在你可以接收
std::pair的两个元素：
(*it).first会得到key，
(*it).second会得到value。这等同于
it->first和it->second。
auto:
C++ auto（类型推导）精讲
auto类型推导：
auto x = 5; // OK: x是int类型 auto pi = new auto(1); // OK: pi被推导为int* const auto *v = &x, u = 6; // OK: v是const int*类型，u是const int类型 static auto y = 0.0; // OK: y是double类型 auto int r; // error: auto不再表示存储类型指示符 auto s; // error: auto无法推导出s的类型
iterator定义中auto的使用：
若无auto：
#include <map> int main(void) {std::map<double, double> resultMap;// ...std::map<double,double>::iterator it = resultMap.begin();for(; it != resultMap.end(); ++it){// do something}return 0; }观察iterator变量it的定义过程，通过 resultMap.begin()，已经能够知道 it 的具体类型了，却非要书写上长长的类型定义才能通过编译。
使用auto后：
#include <map> int main(void) {std::map<double, double> resultMap;// ...for(auto it = resultMap.begin(); it != resultMap.end(); ++it){// do something}return 0; }
map中，排序是按照key值排的，map自带的find方法也是按着key值查找的
C++ map通过key获取value_Android高级知识分享官的博客-CSDN博客_c++ map.get
[STL] map按value值查找——find_if的使用_伐尘的博客-CSDN博客_stl map 查找
C++中map.find()函数_dutmathjc的博客-CSDN博客_map.find() != map.end()
pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。
C++ pair的基本用法总结（整理）_sevencheng798的博客-CSDN博客_c++ pair
