明白了哈希表的原理以及基本的三种哈希结构,接下来我们一起通过几道练习,明白哈希表在解题中应该如何使用
力扣242:有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。
即t是否能由s中的字母组合而成
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true示例 2:
输入: s = "rat", t = "car"
输出: false思路:
我们可以通过哈希结构中的map,键代表的是每个字母,对应的值是该字母出现的次数,先将s中的字母缓存进map中,再遍历t,如果t中的字母没有在map中找到,则返回false,如果找到了则将map中该字母对应的值减一,最后再判断map中字母的值是否都变为0,如果没有都变为0,说明s中的字母t没有全部用到,也返回false
class Solution {
public:bool isAnagram(string s, string t) {unordered_mapmp;//构建底层为哈希表的map映射for(auto i:s){mp[i]++;//遍历s,将s中的字母缓存进map中}for(auto i:t){//遍历tif(mp[i]==0){//如果t中的字母在s中没有出现return false;}else{//出现了则将该字母对应的值减一mp[i]--;}}for(auto i:mp){//判断map中所有的值是否都为0if(i.second!=0){//键值对中值的访问return false;}}return true;}
}; 力扣349:两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的思路:
先遍历nums1,将其中的元素缓存进哈希表中,再遍历nums2,如果nums2中的元素在哈希表中出现了,说明是二者的交集,则将其存入数组.
注意:
由于题目要求输出的结果是唯一的,所以我们可以再用一个哈希表记录存入数组的元素,如果一个元素是交集但是已经被存入数组中了,那我们就不用将其再次存入数组了.
同样的我们也可以使用erase方法,当存入一个元素后,就将该元素从哈希表中删除,在下一次再次遍历到该元素时,由于已经删除,也无法在哈希表中查找到,这样也可以达到输出结果唯一的效果
class Solution {
public:vector intersection(vector& nums1, vector& nums2) {vectorvec;unordered_setst;//记录nums1中的元素unordered_setst2;//记录已经存入数组中的元素for(int i = 0;i
力扣202:快乐数:
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
思路:
根据题意,我们可以将每一次将该数替换为它每个位置上的数字的平方和得到的数存入一个哈希表中,然后重复这个过程,如果发现某一次得到的数已经在哈希表中,说明已经开始循环了,则返回false,如果得到的数为1,则说明是快乐数,返回true
class Solution {
public://将该数替换为它每个位置上的数字的平方和int getNum(int n){int sum = 0;;while(n!=0){int x = n%10;sum+=x*x;n/=10;}return sum;}bool isHappy(int n) {unordered_setst;while(n!=1){//条件判断,当得到的数为1时退出循环if(st.find(n)!=st.end()){return false;//如果在哈希表中找到了该数字,则说明开始循环了}st.insert(n);//未找到就将该数存入哈希表中n = getNum(n);//替换数字}return true;}
};
力扣1:两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
思路:
首先我们需要确定哈希结构的使用,这题中我们可以使用map映射,将元素作为键,元素对应的索引作为值存入
取目标值和数组中每个元素的差值,判断该差值是否在哈希表中,如果在说明当前元素和哈希表中的元素相加可以得到目标值,那我们就返回哈希表中差值对应的值(即差值的索引)和当前的for循环中的i(当前元素的索引).如果该差值不在哈希表中,那我们就将当前元素作为键,索引作为值存入哈希表中
class Solution {
public:vector twoSum(vector& nums, int target) {unordered_mapmp;for(int i = 0;i
力扣454:四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
思路:
对于这种题,如果我们使用四层嵌套for循环,时间复杂度为O(n^4),显然是超出时间限制的.
我们可以优化为先遍历其中的两个数组,得到他们每个元素的加和,将其存入哈希表中,根据题意,若是元组,那么后两个数组中的两个数相加,应该和前两个数组中的加和互为相反数,这样四个元素相加才能变为0.
所以我们可以再遍历后两个数组,得到他们每个数的加和,在哈希表中查找加和的相反数,如果找到说明可以成为元组
这样我们将时间复杂度优化为O(n^2),减少了时间的消耗
注意:
由于前两个数组每个元素的加和可能会出现相同的情况,所以我们可以使用map映射,键为加和,值为加和出现的次数,这样在遍历后两个数组时,就可以直接将出现的次数加上(即前两个数组中有多少个元组能和后两个数组中这种情况匹配),避免少算的情况
例如:
nums1={1,2,3,4} , nums2 = {2,1,5,6},此时加和中会出现两个和为3的情况,所以我们就将哈希表中的mp[3]对应的值设为2,如果nums3和nums4中有和为-3的情况,就可以直接加上mp[3]对应的值为2,避免少算漏算的情况
class Solution {
public:int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {unordered_mapmp;for(auto i:nums1){for(auto j:nums2){int x = i+j;//计算加和if(mp.find(x)==mp.end()){//存入哈希表中mp[x] = 1;}else{mp[x]++;}}}int count = 0;//记录有几个元组for(auto i:nums3){for(auto j:nums4){int z = i+j;//计算后两个数组的加和if(mp.find(-z)!=mp.end()){//查找相反数//找到了就直接加上该数对应的值(即前两个数组中有几个元组加和为该数)count+=mp[-z];}}}return count;}
};