【力扣一轮】202.快乐数 1.两数之和

202.快乐数

力扣链接

代码随想录链接

思路

看到这一题没思路，直接看题解。

发现其中一个难点在于“无限循环”，这个字眼可以转换成退出条件。退出条件就有两种，一种是这个数字是快乐数，一种是这个数字不是快乐数。

如果是快乐数好说，判断结果是否为1即可。如果不是呢？就需要看无限循环。

无限循环的意思翻译下就是判断之后出现的结果，是否在之前的哈希表中存在。如果存在，则说明这个数字是快乐数。

另外一个难点就是怎么对其计算出数字之和？发现用循环解决的。

伪代码

当结果集合不存在1时得到一个计算结果判断这个结算结果是否存在如果存在说明开始循环了返回false将其放入结果集合中
返回true（因为退出循环了）

代码

int getSum(int n ){int sum = 0 ;while(n!=0){sum += (n%10)*(n%10);n /=10;}return sum;
}
bool isHappy(int n) {unordered_set<int> st;n = getSum(n);st.insert(n);while(st.find(1)==st.end()){//等于就相当没找到n = getSum(n);if(st.find(n)!=st.end()){//说明已经有重复的n了return false;}st.insert(n);}//取出数字的每个位置的平方和，放入unorderd_set中return true;
}

1.两数之和

力扣链接

代码随想录链接

思路

刷力扣第一题，刚开始是想暴力，循环两轮取出对应的下标。但因为按照代码随想录刷题，所以借用它的思想，使用哈希表。若使用哈希表，则问题转换为，看哪个元素在集合中出现过？接下来就是这个元素是什么？——应该是target-其中一个元素的差。也就是看差是否出现，以及出现在哪里。

思路想到这里卡住，便去看卡尔讲解视频。

用到了哈希映射，如果这个差没有在集合中，那么就添加到里面；如果在的话，就取出来，作为返回结果。

此时有几个问题要回答。

①为什么会想到用哈希法？

②为什么会想到要用map？以及map，unordered-map，multi-map为什么用第二个？

③map的作用是什么？

④map的key是用来干什么的？为什么key/value不能转换？

问题①，在看到一道题，出现其中一个元素是否存在/出现时，就要考虑是否能使用哈希表？

对应到这道题目，就是在遍历时，需要看这个差是否出现过，若出现，那它的索引是什么。所以，根据这个思考过程，想到用哈希表。

问题②，因为要获取其索引，而差其实是数组元素的数值，索引是另外一个数据，所以需要存储两个元素，数值：索引。就需要用到map。

为什么用unordered-map？因为map和multi-map的底层是红黑树，而unordered-map底层是哈希表，索引查找会更快。

问题③，既然要获取其索引，map的作用在这道题中就是存储暂时不是差的元素。

问题④，key存放的是数值，就是看差是否在map中。如果value存放的是数值，key存放的是索引，那么无法在map中直接通过差查询，而需要遍历，差通过value来比对，会影响效率。

时间复杂度：$O(n)$

空间复杂度：$O(n)$

伪代码

 //只会存在一个有效答案遍历数组，依次查看所需元素是否在map中，如果需要的元素在map中，则返回当前下标以及对应元素下标如果不在map中则将当前元素存入map中返回空

代码

vector<int> twoSum(vector<int>& nums, int target) {map<int , int > mp ;vector<int> vt;for(int i = 0 ; i < nums.size(); i++){int need_num = target - nums[i];map<int, int>::iterator map_result = mp.find(need_num);if (map_result == mp.end()){//这意思就是没找到所需要的元素mp.insert(pair<int,int>(nums[i],i));}else{//存放进{}中vt.push_back(map_result->second);vt.push_back(i);return vt;}}return vt;
}