? ? ? ?当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。? ? ? ? ? ? ? ? ? ? ? ? ?
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
提示：
题目中说了会?无限循环，那么也就是说求和的过程中，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 false
unordered_set<int> result;
while(1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
if (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中寻找是否有匹配的key
auto 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
|