哈希表
《代码随想录》
哈希表一般用来快速查找某个元素是否在一个集合中。如果使用枚举的话时间复杂度为O(n)，而使用哈希表只O(1)就可以做到。——元素查询。
242.有效的字母异位词
使用unordered_map
// 时间复杂度 O(n)// 空间复杂度 O(n)class Solution {public:bool isAnagram(string s, string t) {unordered_map<char,int>mp;for(char& c:s)mp[c]++;for(char& c:t)mp[c]--;for(auto m:mp){if(m.second != 0)return false;}return true;}};
使用数组
// 时间复杂度 O(n)// 空间复杂度 O(1)-因为空间上定义的是一个常量大小的辅助数组class Solution {public:bool isAnagram(string s, string t) {int record[26] = {0};for(char& c:s)record[c-'a']++;for(char& c:t)record[c-'a']--;for(int i = 0 ;i < 26;i++){if(record[i] != 0)return false;}return true;}};
349. 两个数组的交集
unordered_set底层实现同样是哈希表，使用它可以完成去重操作。 因为其中的每一个元素都是唯一的。
// 时间复杂度O(n)// 空间复杂度O(n)class Solution {public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int>nums1_count;unordered_set<int>ret;for(int& c:nums1)nums1_count.emplace(c);for(int& c:nums2){if(nums1_count.find(c) != nums1_count.end())ret.emplace(c);}return vector<int>(ret.begin(),ret.end());}};
本体限制了用例大小，所以我们同样可以使用数组来进行哈希映射。如果哈希值比较少、特别分散、跨度特别大，使用数组就造成空间的极大浪费。// 时间复杂度 O(n)// 空间复杂度 O(n)class Solution {public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int>ret;int count[1000] = {0};for(int &c:nums1){count[c] = 1;}for(int &c:nums2){if(count[c] == 1){ret.emplace(c);}}return vector<int>(ret.begin(),ret.end());}};
350.两个数组的交集 II
使用两个哈希分别保存nums1和nums2中的元素及元素个数。然后选择一种一个哈希表进行遍历，看另外一个哈希表中是否有相同元素，统一元素选择出现较少的次数，然后push进结果数组ret中。
// 时间复杂度 O(n)// 空间复杂度 O(n)class Solution {public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int>mp1,mp2;vector<int>ret;for(int& c:nums1)mp1[c]++;for(int& c:nums2)mp2[c]++;for(auto k:mp1){if(k.second != 0 && mp2[k.first]){int count = min(k.second,mp2[k.first]);for(int i = 0;i < count;i++){ret.emplace_back(k.first); }}}return ret;}};
使用一个哈希表来存储nums1的元素个数，然后开始遍历nums2,如果哈希表中该元素数量大于1，则–，push到ret中。
// 时间复杂度 O(n)// 空间复杂度 O(n)class Solution {public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int>mp;vector<int>ret;for(int& c:nums1){mp[c]++;}for(int& c:nums2){if(mp[c] > 0){ret.emplace_back(c);mp[c]--;}}return ret;}};
第202题. 快乐数
题目中说了可能会死循环，所以出现已经出现过的数了，直接return false用一个哈希表来保存出现过的数。
// 时间复杂度 O(logn)// 空间复杂度 O(logn)class Solution {public:int getSum(int n){int sum = 0;while(n){int tmp = n%10;sum += tmp*tmp;n /= 10;}return sum;}bool isHappy(int n) {unordered_set<int>st;while(1){int tmp =getSum(n);if(tmp == 1){return true;}else{if(st.find(tmp) != st.end()){// 找到了——出现过return false;}else{// 没找到st.emplace(tmp);}}n = tmp;// 更新}}};
1. 两数之和
“数组中同一个元素在答案里不能重复出现。”,看到这句话，就知道要使用哈希表啦。
// 时间复杂度 O(n)// 空间复杂度 O(n)class Solution {public:vector<int> twoSum(vector<int>& nums, int target) {// 注意: 题目说，只会存在一个有效答案。unordered_map<int,int>map;int n = nums.size();for(int i = 0;i < n;i++){auto iter = map.find(target-nums[i]);if(iter != map.end()){// 找到了return {iter->second,i};}else{// 没有找到map[nums[i]] = i;}}return {};}};
454. 四数相加 II
遍历num1,num2,使用一个哈希表来存储二者元素和出现的可能及对应的次数。遍历num3,num4，使用-减去其中的元素组合和，得到一个差值，并在哈希表中查询是否有这个差值，存在，将其数量累加到结果上。
// 时间复杂度 O(n²)// 空间复杂度 O(n)class Solution {public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int>mp;int ret = 0;for(int& a:nums1){for(int& b:nums2){mp[a+b]++;}}for(int& c:nums3){for(int& d:nums4){if(mp.find(0-c-d) != mp.end()){ret += mp[0-c-d];}}}return ret;}};
383. 赎金信
不是所有时候都使用哈希表的，有时候使用数组可能会获得更高的效率。例如本题中，我们可以得到字符出现的范围，26个字母，可卡开辟出数组的大小。在本体情况下，使用map的空间消耗要比数组大一些，因为map要维护红黑树或者哈希表，而且还要做哈希函数，会更费时。
// 时间复杂度 O(n)// 空间复杂度 O(1)-常量辅助数组class Solution {public:bool canConstruct(string ransomNote, string magazine) {int record[26] = {0};for(char &c:magazine){// 使用magazine去组成ransomNote所以先遍历它record[c-'a']++;}for(char& c:ransomNote){if(record[c-'a'] > 0){record[c-'a']--;}else{return false;}}return true;}};
暴力
// 时间复杂度O(n²)// 空间复杂度O(1)class Solution {public:bool canConstruct(string ransomNote, string magazine) {int nr = ransomNote.size();int mr = magazine.size();for(int i = 0;i< mr;i++){for(int j = 0;j <nr;j++){if(magazine[i] == ransomNote[j]){//找到了一个字符ransomNote.erase(ransomNote.begin()+j);break;//找到了一个字符}}}return ransomNote.size() == 0;}};
15. 三数之和
哈希表法，补充: 详见下图，主要为b去重理解。 即，去除同一个元素出现3次以上引起的重复和用于优化剪枝。
// 时间复杂度 O(n²)// 空间复杂度 O(n)class Solution {public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>>ret;int n = nums.size();sort(nums.begin(),nums.end());// 排序是为了方便去重// a = nums[i] // b = nums[j]// c = 0-a-bfor(int i = 0; i < n;i++){// aif(nums[i] > 0){// 排完序了，第一个a还是正数，无法求和==0break;}if(i > 0 && nums[i] == nums[i-1]){// a去重continue;}unordered_set<int>set;for(int j = i + 1;j < n;j++){// bif(j > i+2 &&nums[j] == nums[j-1] &&nums[j-1] == nums[j-2]){// b去重continue;}int c = 0-nums[i]-nums[j];// cif(set.find(c) != set.end()){// 找到了ret.push_back({nums[i],nums[j],c});set.erase(c);// c去重}else{// 没找到，将当前元素b放入set.insert(nums[j]);}}}return ret;}};
双指针: 本题目中使哈希法并不合适，因为在去重的操作中有许多细节需要注意。相对于哈希法，本题使用双指针法会更高效些。 注意: 题目中的不能重复，指的是一个组合不能重复，而组合内的三个元素是可以有重复的。在遍历第一个元素时候，去重的判断,就应该为nums[i] == nums[i-1]： 若为nums[i] == nums[i+1],则为与组合内的元素对比。因为右边的第一个元素为left。 其中一个较难点是对b,c去重的理解。详见代码中的注释。
// 时间复杂度 O(n²)// 空间复杂度 O(n)class Solution {public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>>ret;sort(nums.begin(),nums.end());int n = nums.size();for(int i = 0; i < n;i++){if(nums[i] > 0)break;// 剪枝if(i > 0 && nums[i] == nums[i-1]){// a去重continue;}int left = i+1;int right = n-1;while(right > left){int tmpSum = nums[i] + nums[left] + nums[right];if( tmpSum > 0)right--;else if(tmpSum < 0)left++;else{// 找到结果了ret.push_back(vector<int>{nums[i],nums[left],nums[right]});// b c去重,例如: 已知两个数的和为0，知道其中的一个数，另一个数就是确定的了，所以来两个要收缩。// 当前数与下一个数进行判断是否相同while(right > left && nums[right] == nums[right-1])right--;while(right > left && nums[left] == nums[left+1])left++;// 上面两个循环最终停在上一个元素的最后一次(前/后)出现的位置// 当我们确定一个a之后，b+c的和就确定了；// 进一步说，如果b+c = 5，即b=1的时候，c只能为4，// 所以b c如果与之前相同，都要跳过，即left++/right++(如上面两个while中所示)// 所以左右边界同时收缩，即完成去重。// 下面收缩后，left right 都为下一个与之前计算收集结果时不同的元素。left++;right--;}}}return ret;}};
18. 四数之和
双指针法
// 时间复杂度 O(n³)// 空间复杂度 O(n)class Solution {public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>>ret;int n = nums.size();sort(nums.begin(),nums.end());for(int i = 0; i < n ; i++){if(nums[i] > target && nums[i] > 0){// 剪枝break;}if(i > 0 && nums[i] == nums[i-1])continue;for(int j = i + 1; j < n;j++){// 注意这里判断nums[k]+nums[i] = 0，// 如果后面还有数，当前两个相加为0，大于target，说明target为负数，后面不可能再有答案，0 + 整数 > 0 if(nums[i]+nums[j] > target &&nums[i]+nums[j] >= 0)continue;if(j > i + 1 && nums[j] == nums[j-1])continue;int left = j+1;int right = n-1;while(right > left){// 相加有可能溢出用long存long tmpSum = (long)nums[i]+nums[j]+nums[left]+nums[right];if(tmpSum > target)right--;else if(tmpSum < target)left++;else{ret.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});while(left < right && nums[right] == nums[right-1])right--;while(left < right && nums[left] == nums[left+1])left++;left++;right--;}}}}return ret;}};
如果觉得《【代码随想录】二刷-哈希表》对你有帮助，请点赞、收藏，并留下你的观点哦！
