哈希表哈希表是键值对key-value 存储结构通过哈希函数把 key 映射到数组下标实现平均 O (1) 的增删查改是查询最快的数据结构之一常用的就是unordered_map与unorded_set这些数据结构常用于解决需要快速查找指定元素是否出现过的问题。1.有效的字母异位词力扣题目链接(opens new window)给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。示例 1: 输入: s anagram, t nagaram 输出: true示例 2: 输入: s rat, t car 输出: false说明:你可以假设字符串只包含小写字母。class Solution { public: bool isAnagram(string s, string t) { int record[26]{0}; for(int i0;is.size();i){ record[s[i]-a]; } for(int i0;it.size();i){ record[t[i]-a]--; } for(int i0;i26;i){ if(record[i]!0){ return false; } } return true; } };这里就是直接使用数组即可由于只有小写字母所以这里只需要一个26大小的数组用来记录字符出现的次数先遍历一遍其中字符串记录每个字符串出现的次数在遍历一遍另一个字符串减去个数最终如果数组不全为0即为false2.两个数组的交集力扣题目链接(opens new window)题意给定两个数组编写一个函数来计算它们的交集。class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setint result; unordered_setint set(nums1.begin(),nums1.end()); for(int num:nums2){ if(set.find(num)!set.end()){ result.insert(num); } } return vectorint(result.begin(),result.end()); } };这里就使用unordered_set来解决会自动去重先将一个数组赋值给set之后遍历另一个数组通过查找效率高的特点来进行判断是否是重复的元素再见其插入到结果中3.快乐数力扣题目链接(opens new window)编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果 可以变为 1那么这个数就是快乐数。如果 n 是快乐数就返回 True 不是则返回 False 。class Solution { public: int getsum(int n){ int sum0; while(n){ sum(n%10)*(n%10); nn/10; } return sum; } bool isHappy(int n) { unordered_setint set; while(1){ int sumgetsum(n); if(sum1){ return true; } if(set.find(sum)!set.end()){ return false; } else{ set.insert(sum); } nsum; } } };这里看似为数学问题其实分析不是快乐数的数字就可以得到如果在计算的时候出现了重复出现的数字说明是循环的不是快乐数。所以我们使用unordered_set记录下每次得到的数字如果数字出现过说明就不是快乐数。4.两数之和力扣题目链接(opens new window)给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那 两个 整数并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是数组中同一个元素不能使用两遍。示例:给定 nums [2, 7, 11, 15], target 9因为 nums[0] nums[1] 2 7 9所以返回 [0, 1]class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint,int map; for(int i0;inums.size();i){ auto itmap.find(target-nums[i]); if(it!map.end()){ return {it-second,i}; }else{ map.insert(pairint,int(nums[i],i)); } } return {}; } };这里如果直接暴力的话就是两层for循环效率低题目要求是找到两个数字和为target的两个数返回下标我们可以使用哈希表unordered_mapkey为数字value为位置下标用来记录下每个元素的下标之后再次遍历一遍通过find来进行查找有没有与当前元素和为target的元素找到后可以直接返回结果。5.四数相加II力扣题目链接(opens new window)给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) 使得 A[i] B[j] C[k] D[l] 0。为了使问题简单化所有的 A, B, C, D 具有相同的长度 N且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间最终结果不会超过 2^31 - 1 。class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint,intmap; for(int a:nums1){ for(int b:nums2){ map[ab]; } } int count0; for(int c:nums3){ for(int d:nums4){ if(map.find(0-(cd))!map.end()){ countmap[0-(cd)]; } } } return count; } };这里其实与第一题有效的字母异位词是类似的我们先记录下前两个数组的两个数的和与对应的数量之后再遍历另外两个数组找到和为0的哈希元素后数量就加上对应的value即数量。6. 赎金信力扣题目链接(opens new window)给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成返回 true 否则返回 false。(题目说明为了不暴露赎金信字迹要从杂志上搜索各个需要的字母组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)class Solution { public: bool canConstruct(string ransomNote, string magazine) { int nums[26]{0}; for(int i0;iransomNote.size();i){ nums[ransomNote[i]-a]; } for(int i0;imagazine.size();i){ nums[magazine[i]-a]--; } for(int i0;i26;i){ if(nums[i]0){ return false; } } return true; } };这里与有效的字母异位词是一样的只不过是判断条件不同这里两个字符串的长度不是完全一致的只需要判断其中一个字符串包含另一个字符串就可以了所以如果数组中有的元素的值如果大于0说明不成立。7.三数之和力扣题目链接(opens new window)给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有满足条件且不重复的三元组。注意答案中不可以包含重复的三元组。示例给定数组 nums [-1, 0, 1, 2, -1, -4]满足要求的三元组集合为 [ [-1, 0, 1], [-1, -1, 2] ]class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint result; sort(nums.begin(),nums.end()); for(int i0;inums.size();i){ if(nums[i]0){ break; } if(i0nums[i]nums[i-1]){ continue; } int lefti1; int rightnums.size()-1; while(rightleft){ if(nums[i]nums[right]nums[left]0){ right--; }else if(nums[i]nums[right]nums[left]0){ left; }else{ result.push_back(vectorint{nums[i],nums[left],nums[right]}); while(rightleftnums[right]nums[right-1]){ right--; } while(rightleftnums[left]nums[left1]){ left; } left; right--; } } } return result; } };如果使用哈希表来进行的话记录两个数字再去找另一个数字可行但是去重其实比较麻烦。所以可以考虑使用双指针的做法先进行排序因为如果找的第一个数为大于零的直接返回结果就可以了后面肯定也是大于零的之后再去重一次上一个元素的值与当前元素的值一致说明重复了continue遍历下一个元素之后再判断当前元素的后面元素通过判断当前元素与left与right的和的大小大于零right就要左移反之left右移相等的话就记录其中的一个结果之后还需要再次去重一遍左右指针再次去重将与left与right值相同的给去除之后再更新left与right。最后返回结果就可以了。8.四数之和力扣题目链接(opens new window)题意给定一个包含 n 个整数的数组 nums 和一个目标值 target判断 nums 中是否存在四个元素 abc 和 d 使得 a b c d 的值与 target 相等找出所有满足条件且不重复的四元组。注意答案中不可以包含重复的四元组。示例 给定数组 nums [1, 0, -1, 0, -2, 2]和 target 0。 满足要求的四元组集合为 [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint result; sort(nums.begin(),nums.end()); for(int i0;inums.size();i){ if(nums[i]0nums[i]target){ break; } if(i0nums[i]nums[i-1]){ continue; } for(int ki1;knums.size();k){ if((nums[i]nums[k])target(nums[i]nums[k])0){ break; } if(ki1nums[k]nums[k-1]){ continue; } int leftk1; int rightnums.size()-1; while(rightleft){ if((long)nums[i]nums[k]nums[left]nums[right]target){ right--; }else if((long)nums[i]nums[k]nums[left]nums[right]target){ left; } else{ result.push_back(vectorint{nums[i],nums[k],nums[left],nums[right]}); while(rightleftnums[right]nums[right-1]){ right--; } while(rightleftnums[left]nums[left1]){ left; } left; right--; } } } } return result; } };这里其实与三树之和是一样的不过是在for循环中再次嵌套一层去重也是类似的。总结一般需要使用哈希表的题目主要是需要查找某元素或者需要记录元素的相关信息的题目。这里使用的数据结构也需要根据题目来解决可以使用数组unordered_map或者unordered_set不同的数据结构的作用也不一样主要的目的都是利用查找指定元素效率高的特点