打卡第六天，补昨天的卡

今日任务

• 哈希表理论基础
• 242.有效的字母异位词
• 349.两个数组的交集
• 202.快乐数
• 1.两数之和

哈希表理论基础

哈希表是根据关键码的值而直接进行访问的数据结构。

哈希表能解决什么问题呢?

一般哈希表都是用来快速判断一个元素是否出现集合里。

常见的三种哈希表：

• 数组
• set(集合):
• map(映射):

242.有效的字母异位词

我的解题

class Solution {
public:bool isAnagram(string s, string t) {if(s.size() != t.size()) return false;int hash[26] = {0};for(int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] ++;}for(int i = 0; i < t.size(); i++) {hash[t[i] - 'a'] --;}for(int i = 0; i < 26; i++) {if(hash[i] != 0) return false;}return true;}
};

把s的每一个字符丢进哈希表，然后遍历 t ，判断每个字符是否都出现在哈希表中，并且数量相同，多一个少一个都是false。

349.两个数组的交集

我的解题

暴力做法

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> res;sort(nums2.begin(), nums2.end());for(int i = 0; i < nums2.size(); i++) {for(int j = 0; j < nums1.size(); j++) {if(nums1[j] == nums2[i]) {if(i > 0 && nums2[i - 1] == nums2[i]) break;res.push_back(nums1[j]);break;    }}}return res;}
};

将 nums2 排序，为什么要排序，因为题目要求结果每一个元素要唯一，排完序，当我们判断，后一个元素等于前一个元素，就可以直接跳过这个元素，这样不会造成结果元素不唯一。

返回第一层循环遍历 nums2，选定一个 nums2 元素，第二层循环遍历 nums1，查找nums1中是否有与 选定的 nums2 元素 相等的元素，有就存入结果集，并且跳出第二层循环，如果不 break，结果会重复。

哈希法

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {sort(nums2.begin(), nums2.end());unordered_set<int> mySet(nums1.begin(), nums1.end());vector<int> res;// for(int i = 0; i < nums1.size(); i++) {//     mySet.insert(nums1[i]);// }for(int i = 0; i < nums2.size(); i++) {if(mySet.find(nums2[i]) != mySet.end()) {if(i > 0 && nums2[i] == nums2[i - 1]) continue;res.push_back(nums2[i]);}	}return res;}
};

把 nums1 全部丢进去 unordered_set，循环遍历nums2，当在哈希表找到了于 nums2 相同的元素，存入结果集。

代码随想录

set做法

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重unordered_set<int> nums_set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2的元素 在nums_set里又出现过if (nums_set.find(num) != nums_set.end()) {result_set.insert(num);}}return vector<int>(result_set.begin(), result_set.end());}
};

拓展：

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。

数组做法

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {int hash[1010] = {0};unordered_set<int> res;for(int i = 0; i < nums1.size(); i++) hash[nums1[i]] = 1;for(int i = 0; i < nums2.size(); i++) {if(hash[nums2[i]]) res.insert(nums2[i]);}return vector<int>(res.begin(), res.end());}
};

202.快乐数

我的解题

class Solution {
public:int work(int n) {int res = 0;while(n) {res += (n % 10) * (n % 10);n /= 10;}return res;} bool isHappy(int n) {unordered_set<int> mySet;while(mySet.find(n) == mySet.end()) {mySet.insert(n);n = work(n);if(n == 1) return true; }return false;}
};

计算 该数每个位置上的数字的平方和。

int work(int n) {int res = 0;while(n) {res += (n % 10) * (n % 10);n /= 10;}return res;
} 

每一次计算都要判断是不是等于1，等于1就是快乐数，那什么时候不是快乐数，如果每一次计算每个位置上的数字的平方和 与前面某一次计算结果一样，就永远不可能等于 1。

例如示例2：
$2=0+2^2=4$
$4=0+4^4=16$
$16=1^2+6^2=37$
$37=3^2+7^2=58$
$58=5^2+8^2=89$
$89=8^2+9^2=145$
$145=1^2+4^2+5^2=42$
$42=4^2+2^2=20$
$20=2^2+0=4$

接下来继续计算，结果会一直循环，永远不会等于1。
所以用一个哈希表存储之前计算的结果，每次都判断是否跟之前结果重复，重复就返回 false。

代码随想录

！！！当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

class Solution {
public:// 取数值各个位上的单数之和int getSum(int n) {int sum = 0;while (n) {sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {unordered_set<int> set;while(1) {int sum = getSum(n);if (sum == 1) {return true;}// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return falseif (set.find(sum) != set.end()) {return false;} else {set.insert(sum);}n = sum;}}
};

1.两数之和

我的解题

暴力做法

两层循环，先找一个数，再往后找一个数，相加判断是否等于target，不等于继续找，直到找到。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> res(2);for(int i = 0; i < nums.size(); i++) {for(int j = i + 1; j < nums.size(); j++) {if(target == nums[i] + nums[j]) {res[0] = i;res[1] = j;return res;}}}return res;}
};

不成功的哈希法

我一开始的想法是开一个 unorder_map ，把nums的数跟下标存进去，然后遍历寻找哈希表里是否有 target - nums[i]，有的话就是找到结果。

但是后面发现我这样做，会重复选择两个元素相加，比如示例2，结果会是[0, 0]。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> myMap;for(int i = 0; i < nums.size(); i++) {myMap.insert(pair<int, int> (nums[i], i));}for(int i = 0; i < nums.size(); i++) {auto iter = myMap.find(target - nums[i]);if(iter != myMap.end()) return { i, iter->second};}return {};}
};

代码随想录

本题其实有四个重点：

• 为什么会想到用哈希表？
  需要快速寻找一个数(target - nums[i])，所以考虑用哈希法

• 哈希表为什么用map？
  题目需要返回的是下标，我们找的是值，需要存储两个数据，而map 是以键值对（pair类型）的形式存储数据，比较合适。

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

  因为map是存放访问过的元素，所以不会出现同一个元素在答案里重复出现的情况。因为当我们选择当前这个元素的时候，map里面只有在此之前访问过的元素，没有当前这个元素，所以像示例2，结果不会出现[0, 0]这个情况。

• map中的key和value用来存什么的？
  map 的 key存放数组的元素，value存放数组元素的下标。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> myMap;for(int i = 0; i < nums.size(); i++) {auto iter = myMap.find(target - nums[i]);if(iter != myMap.end()) return { i, iter->second};myMap.insert(pair<int, int>(nums[i], i));}return {};}
};