哈希表
1. 哈希表理论基础
哈希表有一个现象：哈希冲突
解决哈希冲突的方法：拉链法，线性探测法
常见的三种哈希结构：
- 数组
- set
- map
哈希查找：O(1)
枚举查找：O(n)
红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
2. 有效的字母异位词
242. 有效的字母异位词【简单】
思路一：sort()函数先对字符串进行排序，在判断两个字符串相等。时间复杂度高
思路二：桶排序；对字符串1进行++计数；对字符串2进行–计数；判断最后桶中是否都为0
思路三：哈希表计数；思路还是桶排序的思路，只是用哈希表实现
代码只记录思路三的，其他两个不写。
时间复杂度：O(n) n为字符串长度
空间复杂度：O(S) S为字符集大小
class Solution { public: bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; //字符串长度不相等 false unordered_map<char, int> map; for (int i = 0; i < s.size(); i++) { //计数；一个++；一个-- map[s[i]]++; map[t[i]]--; } for (auto p : map) { if (p.second != 0) return false; //最后计数必须为0 } return true; } };
383. 赎金信【简单】
题目意思：判断字符串a中的字符能不能构成字符串b
思路一：sort()排序+双for暴力枚举
思路二：暴力枚举+erase()函数
// 时间复杂度: O(n^2) // 空间复杂度：O(1) class Solution { public: bool canConstruct(string ransomNote, string magazine) { for (int i = 0; i < magazine.length(); i++) { for (int j = 0; j < ransomNote.length(); j++) { // 在ransomNote中找到和magazine相同的字符 if (magazine[i] == ransomNote[j]) { ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符 break; } } } // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote if (ransomNote.length() == 0) { return true; } return false; } };
思路三：桶排序；26个桶统计字符个数
思路四：哈希表计数；主串计数++；子串计数–；判断计数后是否有<0的。
下面记录思路二的代码
class Solution { public: bool canConstruct(string ransomNote, string magazine) { if (magazine.size() < ransomNote.size()) return false; //排除子串长度大于主串的情况 unordered_map<char, int> map; for (auto i : magazine) { map[i]++; } for (auto i : ransomNote) { map[i]--; } for (auto p : map) { if (p.second < 0) return false; } return true; } };
49. 字母异位词分组【中等】
思路：哈希表
这题有点难度；前序后的作为模板，即作为键；排序前的作为能匹配到模板的值
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string>> map; for (auto str : strs) { string key = str; sort(key.begin(), key.end()); //排序后的作为键 //这句代码可以换成其他的实现排序 map[key].emplace_back(str); //排序前的作为值 } vector<vector<string>> res; for (auto p : map) { res.push_back(p.second); //一下子插入一个vector<string> } return res; } };
438. 找到字符串中所有字母异位词【中等】
思路一：用一个桶计数并滑动窗口
//滑动窗口：一边延伸，一边缩进 //用一个桶计数 class Solution { public: bool equal(int* tong) { for (int i = 0; i < 26; i++) { if (tong[i] != 0) return false; } return true; } vector<int> findAnagrams(string s, string p) { if (p.size() > s.size()) return vector<int>(); //排除子串比主串长的情况 vector<int> ans; //用于存储索引 int tong[26] = { 0 }; for (int i = 0; i < p.size(); i++) { tong[p[i] - 'a']--; tong[s[i] - 'a']++; } for (int i = p.size(); i <= s.size(); i++) { if (equal(tong)) { ans.push_back(i - p.size()); } if (i != s.size()) { //防止索引越界 tong[s[i] - 'a']++; //实现滑动 tong[s[i - p.size()] - 'a']--; } } return ans; } };
//滑动窗口：一边延伸，一边缩进 //用一个桶计数 class Solution { public: bool equal(int* tong) { for (int i = 0; i < 26; i++) { if (tong[i] != 0) return false; } return true; } vector<int> findAnagrams(string s, string p) { if (p.size() > s.size()) return vector<int>(); //排除子串比主串长的情况 vector<int> ans; //用于存储索引 int tong[26] = { 0 }; for (int i = 0; i < p.size(); i++) { tong[p[i] - 'a']--; tong[s[i] - 'a']++; } if (equal(tong)) ans.push_back(0); for (int i = 0; i < s.size() - p.size(); i++) { tong[s[i] - 'a']--; //实现滑动 tong[s[i + p.size()] - 'a']++; if (equal(tong)) ans.push_back(i + 1); } return ans; } };
或者用两个容器，其实都一样，只是判断相等的语句换了
class Solution { public: vector<int> findAnagrams(string s, string p) { if (s.size() < p.size()) return vector<int>(); vector<int> ans; vector<int> sCount(26); vector<int> pCount(26); for (int i = 0; i < p.size(); ++i) { sCount[s[i] - 'a']++; pCount[p[i] - 'a']++; } if (sCount == pCount) ans.emplace_back(0); for (int i = 0; i < s.size() - p.size(); i++) { //需要滑动的次数 sCount[s[i] - 'a']--; sCount[s[i + p.size()] - 'a']++; if (sCount == pCount) ans.emplace_back(i + 1); } return ans; } };
思路：滑动窗口哈希表
时间复杂度和空间复杂度都很高；这里不推荐此方法
class Solution { public: bool equal(unordered_map<char, int> map) { for (auto p : map) { if (p.second != 0) return false; } return true; } vector<int> findAnagrams(string s, string p) { if (p.size() > s.size()) return vector<int>(); unordered_map<char, int> map; for (int i = 0; i < p.size(); i++) { map[p[i]]--; map[s[i]]++; } vector<int> res; if (equal(map)) res.push_back(0); for (int i = p.size(); i < s.size(); i++) { map[s[i]]++; map[s[i - p.size()]]--; if (equal(map)) res.push_back(i - p.size() + 1); } return res; } };
滑动窗口优化
都是在优化判断相等的方法：统计不为0的个数来判断相等
class Solution { public: vector<int> findAnagrams(string s, string p) { int sLen = s.size(), pLen = p.size(); if (sLen < pLen) { return vector<int>(); } vector<int> ans; vector<int> count(26); for (int i = 0; i < pLen; ++i) { ++count[s[i] - 'a']; --count[p[i] - 'a']; } int differ = 0; for (int j = 0; j < 26; ++j) { if (count[j] != 0) { ++differ; } } if (differ == 0) { ans.emplace_back(0); } for (int i = 0; i < sLen - pLen; ++i) { if (count[s[i] - 'a'] == 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同 --differ; } else if (count[s[i] - 'a'] == 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同 ++differ; } --count[s[i] - 'a']; if (count[s[i + pLen] - 'a'] == -1) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同 --differ; } else if (count[s[i + pLen] - 'a'] == 0) { // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同 ++differ; } ++count[s[i + pLen] - 'a']; if (differ == 0) { ans.emplace_back(i + 1); } } return ans; } };
3. 两个数组的交集
349. 两个数组的交集【简单】
思路一：枚举暴力破解；时间复杂度O(mn)
思路二：sort函数排序+双指针指向两个数组开始遍历；
时间复杂度O(nlogn+mlogm) ；
空间复杂度：O(logm+logn)； 主要取决于排序使用的额外空间
思路三：哈希表可以实现去重；
时间复杂度O(n+m)
空间复杂度O(n+m)
class Solution { public: //哈希表存数 unordered_set无序，每种元素只能存储一个； set是有序的 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> s1, s2; for (auto& i : nums1) s1.insert(i); //存元素且去重，保证唯一 for (auto& i : nums2) s2.insert(i); vector<int>v; for (auto& i : s2) { //遍历s2中的每一个元素 在s1中进行查找 if (s1.count(i)) v.push_back(i); } return v; } };
或者以下：
空间复杂度O(m)
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> set; for (auto i : nums1) { //只存num1的 set.insert(i); } vector<int> res; for (auto i : nums2) { //遍历num2中的每一个元素，在set中进行查找 找到了要在哈希表中删除该元素 保证唯一 if (set.count(i)) { //查询的时间复杂度也为O(1) res.push_back(i); set.erase(i); //删除的时间复杂度为O(1) } } return res; } };
350. 两个数组的交集 II【简单】
思路一：排序+双指针指向两个数组；该方法比349的还要简单了
思路二：哈希表计数。因同种元素要计算次数了，由unordered_set改成unordered_map
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> map; //第二个int为元素的次数 for (auto i : nums1) { map[i]++; } vector<int> res; for (auto i : nums2) { if (map.count(i) && map[i] > 0) { //找到了该元素 且个数>0才行 res.push_back(i); map[i]--; //消消乐抵消一个 } } return res; } };
4. 快乐数
202. 快乐数【简单】
思路：我们可以认为之前出现过的数之后不会出现，即不成环，则总有一天走到1
如果成环，则不是快乐数
主要是看懂题目，看懂了题目就很简单。
class Solution { public: int getSum(int n) { //获取下一个个数 int res = 0; while (n) { res += (n % 10) * (n % 10); n = n / 10; } return res; } bool isHappy(int n) { unordered_set<int> set; while (true) { int next_sum = getSum(n); //1的下一个数也是1 所以这句代码可以写前面那 if (next_sum == 1) return true; if (set.count(next_sum)) return false; //成环 else set.insert(next_sum); //没成环 n = next_sum; } } };
5. 两数之和
1. 两数之和【简单】
思路一：双for循环暴力枚举
思路二：哈希表+遍历查询，因为返回索引，索引用unordered_map
思路二代码如下：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> map; for (int i = 0; i < nums.size(); i++) { if (map.count(target - nums[i])) return { i, map[target - nums[i]] }; map[nums[i]] = i; //map插入元素 因为答案唯一，不需要担心插入两个相同的元素 } return {-1,-1}; //这句代码走不到 } };
454. 四数相加 II【中等】
思路一：4for暴力枚举；不用多想，肯定超超时
思路二：4for拆开成两个两个，第一个双for存入哈希表，第二个双for查找哈希表
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> map; for (auto num1 : nums1) { for (auto num2 : nums2) { map[num1 + num2]++; } } int res; for (auto num3 : nums3) { for (auto num4 : nums4) { if (map.count(-num3 - num4)) { res += map[-num3 - num4]; //有几个这样的就加几 } } } return res; } };
15. 三数之和【中等，双指针】
思路：排序+双指针
哈希表时间复杂度和空间复杂度都很高
难度主要在于降重
时间复杂度：O(n^2)
空间复杂度：O(1)
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); // 找出a + b + c = 0 a = nums[i], b = nums[left], c = nums[right] for (int i = 0; i < nums.size(); i++) { // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组 if (nums[i] > 0) return result; // 正确去重方法 if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.size() - 1; while (right > left) { // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组 if (nums[i] + nums[left] + nums[right] > 0) { right--; } else if (nums[i] + nums[left] + nums[right] < 0) { left++; } else { result.push_back(vector<int>{nums[i], nums[left], nums[right]}); // 去重逻辑应该放在找到一个三元组之后 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 找到答案时，双指针同时收缩 right--; left++; } } } return result; } };
18. 四数之和【中等】
与上一题思路一样
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int k = 0; k < nums.size(); k++) { // 去重 if (k > 0 && nums[k] == nums[k - 1]) { continue; } for (int i = k + 1; i < nums.size(); i++) { // 正确去重方法 if (i > k + 1 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.size() - 1; while (right > left) { if (nums[k] + nums[i] > target - (nums[left] + nums[right])) { right--; } else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) { left++; } else { result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]}); // 去重逻辑应该放在找到一个四元组之后 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 找到答案时，双指针同时收缩 right--; left++; } } } } return result; } };
else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) { left++; } else { result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]}); // 去重逻辑应该放在找到一个四元组之后 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 找到答案时，双指针同时收缩 right--; left++; } } } } return result; }
