代码随想录-day8 哈希表(2)

题目分析：
本题的暴力思路就是对p进行排序，然后对s中的每一个字串进行排序，理论上可以求出结果，但是不断的排序导致时间复杂度非常高，直接超出时间限制，所以是不可行的。
本题可以使用哈希表加滑动窗的思路进行：
首先根据p出现的字数建立哈希表，然后s也根据p的长度同时建立次数哈希表，一旦两个哈希表相等，就代表异位词出现了。不管出现还是没出现，s字符串中长位lenP的窗都要移动一位。
由于字母的数量是有限的，所以我们使用数组来实现哈希表。

题目解答：

class Solution {
public:vector<int> findAnagrams(string s, string p) {// 本题实际上可以使用滑动窗口结合哈希表的思路来解决// 由于字母的数量是有限的，所以可以用数组来实现哈希表int lenS = s.size();int lenP = p.size();if (lenS < lenP) return {};vector<int> ans;vector<int> countS(26, 0);vector<int> countP(26, 0);for (int i = 0; i < lenP; i++) {countP[p[i] - 'a']++;  // 统计p中每个字母出现的次数countS[s[i] - 'a']++;  // 统计s中前lenP个字母出现的次数}if (countP == countS) ans.emplace_back(0);  // 如果正好相等了，那么第一个异位词的起始就是0// 滑动窗口for (int i = 0; i < lenS - lenP; i++) {countS[s[i] - 'a']--;  // 开始进来是0，前面已经判断过了，肯定不是，所以清除这，后面就相当于一个一个向后移动countS[s[i + lenP] - 'a']++;  // 前面移动，后面也要移动if (countS == countP) ans.emplace_back(i + 1);  // i+1才是入口}return ans;}
};

题目分析：
求两个数组的交集，而且不考虑重复的元素，本题就是一个典型的使用set的哈希表的题目。
两个特点：

• 不重复
• 一个元素在不在另一个集合里面

所以考虑使用set来进行操作，而unordered_set底层使用哈希表实现，查询速度最快。

题目解答：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> set1(nums1.begin(), nums1.end());  // 使用初始化的方法定义set1unordered_set<int> res;    for (auto num : nums2) {if (set1.find(num) != set1.end()) {  // 如果查询到了，就加到结果中res.emplace(num);}}return vector<int>(res.begin(), res.end());  // 注意这种返回的方式}
};

实际上，这个题目给定了数组的长度[1,1000]以及数组中每个数的大小限制，我们可以直接用数组来实现哈希表。一个关键的过程就是，一旦出现了，我就认为你出现的次数是1，这样也就达到了去重的目的。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 由于这个题目给定了nums的长度以及num的大小上限，可以使用数组来实现哈希表vector<int> hash(1001, 0);vector<int> ans;for (auto& num : nums1) {hash[num] = 1;  // 只要你出现过，次数就是一次，这里的作用和set本质上就是一样的了}for (auto& num : nums2) {if (hash[num] == 1) {  // 在nums1中出现过的数字在nums2中也出现了ans.emplace_back(num);hash[num]--;  // 为了避免nums2中还有相同的，这里直接让hash[num]--，避免重复}}return ans;}
};

题目分析：
这个题还是求交集，跟之前的那道题目不同的是，这个题要求如果存在重复的元素，也要输出出来，那么这道题就不能使用set来做，因为重复是考虑在我们的里面的。
首先使用map来统计nums1中的每个数字出现的次数，然后遍历nums2数组，如果发现其中的值也在nums1中，就将其加到结果中，否则跳过即可，注意匹配过的数字，在nums1中也要相应减1。

题目解答：

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {// 使哈希表统计nums1中各个元素出现的次数unordered_map<int, int> umap;vector<int> ans;// umap[num]需要初始化吗，有一说一，c++默认操作，如果见不存在，则会创建一个新的键，值是0for (int num : nums1) umap[num]++;  // 统计出现的次数for (int num : nums2) {if (umap[num] != 0) {  // 一旦在nums1中出现的元素在nums2中出现了，就将其存在结果中umap[num]--;ans.emplace_back(num);}}return ans;}
};

这里有一个需要注意的地方，就是map的值的初始化问题，自增统计次数到底有没有意义。
chatgpt的回答：对于每个 num，umap[num]++ 操作会首先访问 umap 中对应的键 num，如果 num 不存在，则会创建一个键值对 num:0。因为这个键值对刚刚被创建，所以它的值为 0，接着自增操作将其值变为 1。
注意这里是会自己创建的，所以下面的代码是合理的：

    unordered_map<int, int> umap;cout << umap[100] << endl;

注意：这个题目也给了数组的长度以及数组中数据的最大值，所以我们也可以用数组来实现哈希表，但是会造成大量的空间浪费。

题目分析：
这个题目乍一看是一个数学题，类似于水仙花那种数学题，但是不然。这个题目中有一个非常关键的一句话，如果不是快乐·数，则会陷入无限循环。循环是什么意思，就是能回到原点啊，那么能回到原点的一定就不是快乐数，反之，不能回到原点的总有一次会能满足和为1，即快乐数。
思路理清之后，我们就很明确这道题可以直接用set啊，一旦回来了，就一定不是快乐数。
另外，这个题目还有一个地方也是需要学习的，就是如何巧妙的得到数字的各个位，针对这个问题，我之前做了一个很蠢的事情，那就是题目给出了这个数字的最大值是2^31-1，那就好了，我直接就弄那么多个数，然后得到每一位，具体的做法如下：

    vector<int> getPosition(int n) {// 由于最大的数是2^31 - 1, 也就是2,147,483,647，一共有10位vector<int> res(10, 0);vector<int> num = { (int)1e9, (int)1e8, (int)1e7, (int)1e6, (int)1e5, (int)1e4, (int)1e3, (int)1e2, 10, 1 };int sum = 0;for (int i = 0; i < 10; i++) {for (int j = i - 1; j >= 0; j--) {sum += res[j] * num[j];}res[i] = (n - sum) / num[i];sum = 0;}return res;}

大概的意思就是说，比如我要获取1234，我直接用1234/1000 = 1，这就是第一位，然后第二位就是（1234-11000）/100=2，第三位：（1234-11000-2*100）/10=3，第四位就是4，总之来说非常蠢。
其实一般而言，我们获取数字的每一位，并不是从前往后，而是从后往前不断获取。可以使用递归或者循环来实现。

void getPosition(int num) {// 使用递归来实现int s = 0;if (num > 0) {s = num % 10;cout << s << " ";getPosition(num / 10);}
}

void getPosition(int num){// 使用循环来实现int s = 0;while (num) {s = num % 10;cout << s << " ";num /= 10;	}
}

然后接下来就是很简单的操作了。

class Solution {
public:bool isHappy(int n) {unordered_set<int> uset;uset.emplace(n);  // 如果不是快乐数的话，也迟早循环到这个数int sum = getSum(n);while (1) {if (sum == 1) return true;  // 如果和为1，直接返回if (uset.find(sum) != uset.end()) return false;  // 如果找到了，说明这个就不是快乐数else {uset.emplace(sum);sum = getSum(sum);}}return false;}// 得到和int getSum(int& n) {int sum = 0;while (n) {int temp = n % 10;sum += temp * temp;n /= 10;}return sum;}
};

题目分析：
这个题的暴力思路其实非常简单，一个一个遍历，然后从下一个元素开始遍历，一旦二者的和是target，直接返回即可。但是这样的暴力算法的时间复杂度为O(n)，十分耗时。
我们前面提到的可以用set以及数组来实现哈希表，但是这个题就是典型的使用ma的题目，因为它不仅要求我们存储值，还要求返回坐标呢。
具体的思路就是，依次遍历数组中的元素，如果target-num不在哈希表中，那么就添加进去，键为num的值，值为num的位置，因为我们map的查找是查找的键。
题目解答：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> umap;vector<int>  ans;for (int i = 0; i < nums.size(); i++) {auto it = umap.find(target - nums[i]);if (it == umap.end()) umap[nums[i]] = i;  // ==end()就代表找不到else return {umap[target - nums[i]], i};  // 如果找到了，那就把target-num[i]的坐标和当前的i返回}return {};}
};

题目分析：
本题的难度不大，分析如下：

• 首先是本题的数组是分开的，那就不考虑到重复的问题，跟后面的三数之和以及四数之和是不一样的；
• 本题只要求返回有多少个元组，并没有要求你返回这些元组。
  本题的思路如下，四个数组两两一组，定义一个哈希表，哈希表的键为两个数组的和的组合出现的次数，然后寻找另外两个数组的和的键是不是在哈希表中出现过，出现过几次最终的答案就是几次。

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {// 使用哈希表来做，弄清楚本题的实质unordered_map<int, int> umap;  // 键是a+b，值是a+b出现的次数int ans = 0;  // 结果for (auto& a : nums1) {for (auto& b : nums2) {umap[a + b]++;  // 这句话就可以统计出键a+b的值的次数了}}for (auto& c : nums3) {for (auto& d : nums4) {if (umap.find(- c - d) != umap.end()) {  // 说明c+d在umap中出现过ans += umap[- c - d];  // 一旦出现了，就能跟umap中的进行组合。这里是加的-c-d出现的次数}}}return ans;}
};

注意： 这里ans每次加的是umap[-c-d]，也就是每出现一次，就可以和之前的所有情况进行组合。两次写代码都写成了ans++；非常严重的错误。
如果这个题不仅要求返回个数，同时要求返回元组呢？

vector<vector<int>> fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, vector<vector<int>>> umap;  // 键是a+b，值是a+b出现的次数int len = nums1.size();vector<vector<int>> ans;for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {umap[nums1[i] + nums2[j]].push_back({i, j});  // 这句话就可以统计出键a+b的值的次数了}}for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {auto it = umap.find(-nums3[i] - nums4[j]);if (it != umap.end()) {  // 说明c+d在umap中出现过vector<vector<int>> temp = it->second;int count = temp.size();  // umap中相反数出现的次数，对应不同的组合for (int k = 0; k < count; k++) {temp[k].push_back(i);  // 对每一个和出现的情况的vector末尾追加i和jtemp[k].push_back(j);ans.push_back(temp[k]);}}}}return ans;
}int main() {vector<int> nums1 = {-1,-1}, nums2 = {-1,1}, nums3 = {-1,1}, nums4 = {1,-1};vector<vector<int>> res = fourSumCount(nums1, nums2, nums3, nums4);for (int i = 0; i < res.size(); i++) {for (int j = 0; j < res[0].size(); j++) {cout << res[i][j] << " ";}cout << endl;}return 0;
}

结果如图所示：

今天接触哈希表的第二天，对哈希表的认识更近了一步。当涉及查找一个元素是不是在集合里面的时候，考虑使用哈希表。如果要求不重复，优先使用set，如果可以确定数组的大小，可以使用数组实现哈希表，如果牵涉到要存映射数据，比如第6题，就考虑使用map来解决。
要在这个世界上获得成功，就必须坚持到底：至死都不能放手。——伏尔泰