哈希表

LC41 要求 O(n) 时间 O(1) 空间找第一个缺失正整数，常规哈希表空间不够用。原地哈希的核心思路：数组本身就是一张哈希表，把每个数送回它该在的位置。

快乐数的本质是判环问题。从「为什么一定成环」到「为什么快慢指针一定相遇」，把 Floyd 算法的直觉讲清楚。

454. 四数相加II 链接：力扣454 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 two sum的变形，把数组两两分组之后变成two sum； 看完题解后的想法 —— 实现中遇到的困难 这里最开始看到分组都要两层循环，时间复杂度达到 $O(n^2)$ ，就觉得在查询逻辑里可以不用哈希直接遍历，因为也是两层循环； 但是这个是要考虑数组大小的，原来的数组大小是 $n$ ，分组求和之后就是 $n^2$ ，如果再两层遍历循环这个 $n^2$ 的数组复杂度就是 $O(n^4)$ ； 代码 class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> hash; int cnt = 0; for (int i = 0; i < nums1.size(); i++) { for (int j = 0; j < nums2.size(); j++) { hash[nums1[i] + nums2[j]]++; } } for (int i = 0; i < nums3.size(); i++) { for (int j = 0; j < nums4.size(); j++) { int sum = nums3[i] + nums4[j]; if (hash.count(-sum) != 0) { cnt += hash[-sum]; } } } return cnt; } }; 383. 赎金信 链接：力扣383 文章：代码随想录 状态：✅ 第一想法 类似于异构词，但是只用部分一致； ...

242. 有效的字母异位词 链接：力扣242 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 这道题要判断两个字符串包含的字符是否完全一致，第一想法就是哈希表； 仔细思考就会发现因为只有26个字符，所以不需要使用完整的哈希表，只需要使用一个定长数组模拟哈希就行了； 看完题解后的想法 —— 实现中遇到的困难 最开始的时候将 s 的写入和判断的 t 的减少分开在了两个循环中，其实一次循环就能做； 代码 class Solution { public: bool isAnagram(string s, string t) { if (s.size() != t.size()) { return false; } int cnt[26] = {}; for (int i = 0; i < s.size(); i++) { cnt[s[i] - 'a']++; cnt[t[i] - 'a']--; } for (int c : cnt) { if (c != 0) { return false; } } return true; } }; 349. 两个数组的交集 链接：力扣349 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 使用集合去重+记录出现元素,之后再用集合去重; ...