哈希表--day4--（leetcode202/leetcode1/leetcode454）

leetcode202. 快乐数

链接

基本思路

实际上题目隐藏着一个小细节，就是告诉你会发生无限循环，那我们该如何跳出这个无限循环就是一个需要想通的点，而在这个过程中，我们通过几次样例的测试或者根据常识的判断，最后发生无限循环的原因，就是存在了出现相同的数，导致陷入了局部无限循环。所以自然而然可以想得到要使用set/vector探索是否会出现相同的数，以此退出无限循环。

AC-code

class Solution {
public://传入n得到新的nint happy(int n){int sum = 0;int tail;while(n){tail = n % 10;n /= 10;sum += tail*tail;}return sum;}bool isHappy(int n) {//题目提示说了可能会出现无限循环，潜台词就是告诉我们对应的n会不断出现循环的值。所以根据题目的意思，我们跳出无限循环的条件就是，判断n是否已经出现过了，出现了就可以跳出，没有出现就继续循环，知道为1.//定义一个set用于储存结果，如果结果出现了相同的值，就进行一个跳出循环，没有就继续训话 。unordered_set<int>set_n;while(n != 1){//当找到了就直接推出无限循环，返回失败if(set_n.find(n) != set_n.end())return false;//插入未出现的数据set_n.insert(n);//进行新一轮运算n = happy(n);}return true;}
};

leetcode1. 两数之和

链接

基本思路

首先这道题，正常人的想法肯定是直接进行两层for循环，进行暴力遍历，但时间复杂度是O(n2)，所以可以进行稍微的修改。

实际上算法的思想就是：一层for循环遍历做两种事情，也就是我们取出对应数组的元素，然后拿target-当前对应数组的元素，将其与与之前所寻找到的元素进行作比较，如果存在就是返回正确答案，不存在就继续循环。

接下来需要明确两点：

map用来做什么
map中key和value分别表示什么
map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

AC-code

暴力的代码：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result(2,0);for(auto i1 = nums.cbegin() ; i1!=nums.cend() ; i1++){int flag = 0;for(auto i2 = i1+1 ; i2!=nums.cend() ; i2++){if(*i1+*i2==target){flag = 1;result[0] = i1-nums.begin();result[1] = i2-nums.begin();break;}}if(flag)break;}return result;}
};

使用map的代码：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//定义哈希数组用于存储已经遍历过的numsunordered_map<int,int >map_nums;//定义一个temp用于存储减值int temp = 0;//for循环遍历nums，并且判断target-num对应的数据是否在map当中出现过，如果出现过就返回，没出现过就继续。for(int i = 0; i != nums.size(); i++){temp = target - nums[i];//判断temp在map当中是否出现过if(map_nums.find(temp) != map_nums.end())return vector<int>{map_nums[temp],i};//如果没找到map_nums.insert(make_pair(nums[i],i));}return vector<int>{};}
};

454.四数相加II

链接

基本思路

本题正常想法肯定是直接四层for循环，进行判断，但这种时间复杂度就是O(n4),那有没有一种方法可以减小时间复杂度呢？答案是有的，实际上就是使用哈希表存储a+b的值，并在循环遍历c+d的时候去哈希表当中寻找是否出现了对应的相反数，如果存在就是满足条件++？（不，是加上出现的次数，好好想想为什么），不存在就继续循环。

1. 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
   定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
3. 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
4. 最后返回统计值 count 就可以了

AC-code

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {//创建哈希表存储nums1+nums2,并且使用map，value就是对应的出现的次数unordered_map<int,int>map_num;//定义result为出现的次数int result = 0;//循环遍历nums1和nums2，统计出现的次数以及值for(auto i : nums1)for(auto j : nums2)++map_num[i+j];//遍历nums3和nums4，并且查询是否出现过，出现过就+对应的次数for(auto i : nums3){for(auto j : nums4){//如果找到了if(map_num.find(0-i-j) != map_num.end()){result += map_num[0-i-j];}}}return result;}
};