202. 快乐数

题目链接：202. 快乐数
题目描述：编写一个算法来判断一个数 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

思路

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
当我们发现要快速判断一个元素是否出现集合里的时候--》考虑哈希法！！！
判断sum是否重复出现就可以使用unordered_set。

class Solution {
public:
    int getSum(int n) {// 取数值各个位上的单数之和
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);//sum=n%10*2 + sum;
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {//当sum重复是1后就返回true
        unordered_set<int> 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;
        }
    }
};

1. 两数之和

题目链接：1. 两数之和
题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思考

本题虽说是力扣的第一题，但是对于初学算法的小白并不友好。着重考察对map的理解与应用，本题思路是需要一个集合去存放我们已经便利过的元素，然后再遍历数组的时候去访问这个集合，不仅要知道这个元素是否遍历过，还需要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。
map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。
同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

1、map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）
2、判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
    	unordered_map(int, int)map;//定义unordered-map是用来存放我们遍历过的元素 
		for(i=0; i<nums.size(); i++){//开始遍历数组 
			s = target - nums[i];//寻找我们要查询的值：eg：第一个为2 则找tar-2的元素值 
			iter = map.find(s); 	//map的一个遍历方式去选找s 
			if(iter  != map.end()){//如果找到元素在map出现过 
			return {iter->valve, i} //返回 元素下标
		}
		 // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i));
		}	
		return {}; //遍历结束还没找到，就返回空集合 
	}
	}

总结

其实有四个重点：
1.为什么会想到用哈希表
2. 哈希表为什么用map
3. 本题map是用来存什么的
4. map中的key和value用来存什么的
把这四点想清楚了，本题才算是理解透彻了。