算法刷题-哈希表

算法刷题-哈希表

242. 有效的字母异位词

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

**注意：**若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

思路

用一个哈希表来记录第一个字符串每个字符出现的次数，然后遍历第二个字符串，减去他的字母出现的次数，

最后如果哈希表每个值都是0，说明符合题意

代码

    bool isAnagram(string s, string t) {map<char,int> m;for(char c:s) m[c]++;for(char c:t) m[c]--;for(auto [x,y]:m) {if(y!=0) return false;}return true;}

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

思路

用一个set记录第一个数组出现了哪些元素，然后再开一个set记录两个数组都出现的元素即可

代码

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> res;set<int> s,s2;for(int x:nums1) s.insert(x);for(int x:nums2){if(s.count(x)) s2.insert(x);} for(int x:s2) res.push_back(x);return res;}

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路

写一个函数f来计算每次变化后的结果

用一个哈希表来存n能变到哪些数字，如果第二次变到哈希表里的数字，说明有循环，退出即可

代码

    int f(int n){int x=0;while(n) x+=(n%10)*(n%10),n/=10;return x;}bool isHappy(int n) {set<int> s;while(1){if(n==1) return 1;if(s.count(n)) return 0;s.insert(n);n=f(n);}}

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路

用一个哈希表记录每个数字出现的位置

再遍历一次数组，如果nums[i]-target在哈希表中存在，说明找到了，直接返回

代码

    vector<int> twoSum(vector<int>& nums, int target) {map<int,int> m;int n=nums.size();for(int i=0;i<n;i++) m[nums[i]]=i;for(int i=0;i<n;i++){int j=m[target-nums[i]];if(j!=0&&j!=i) return {i,j};}return {0,0};}

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

思路

先将nums1和nums2所有可能得到的值的组合存到哈希表中

在遍历nums3和nums4，判断0-nums3[i]-nums4[j]在不在哈希表中

时间复杂度为$O(n^2)$

代码

    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {map<int,int> m;for(int x:nums1)for(int y:nums2)m[x+y]++;int res=0;for(int x:nums3)for(int y:nums4)if(m[0-x-y]!=0)res+=m[0-x-y];return res;}

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

思路

将第二个字符串的每个字符出现的次数存入到哈希表中

在遍历第一个字符串，对应出现的次数减去

最后判断是否有出现次数<0的字母，说明不符合题意

代码

    bool canConstruct(string ransomNote, string magazine) {map<char,int> m;for(char c:magazine) m[c]++;for(char c:ransomNote) m[c]--;for(auto [x,y]:m) if(y<0) return false;return true;}

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

思路

先对数据进行排序，然后遍历一次数组，双指针不断缩小范围

代码

    vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> res;int n=nums.size();for(int k=0;k<n-2;k++){if(nums[k]>0) break;if(k>0&&nums[k]==nums[k-1]) continue;int i=k+1,j=n-1;while(i<j){int sum=nums[k]+nums[i]+nums[j];if(sum<0)while(i<j &&nums[i]==nums[++i]);else if(sum>0) while(i<j && nums[j]== nums[--j]);else{res.push_back({nums[i],nums[j],nums[k]});while(i<j&&nums[i]==nums[++i]);while(i<j&&nums[j]==nums[--j]);}}}return res;}

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

思路

和三数之和一样，双指针算法。

代码

    vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> res;int n=nums.size();for(int k=0;k<n;k++){if(nums[k]>target&&nums[k]>=0) break;if(k>0 &&nums[k]==nums[k-1] ) continue;for(int i=k+1;i<n;i++){if(i>k+1 &&nums[i]==nums[i-1]) continue;int l=i+1,r=n-1;while(l<r){long long sum=(long long)nums[k]+nums[i]+nums[l]+nums[r];if(sum>target) r--;else if(sum<target) l++;else {res.push_back({nums[k],nums[i],nums[l],nums[r]});while(l<r && nums[l]==nums[l+1])l++;while(l<r &&nums[r]==nums[r-1]) r--;r--,l++;}}}}return res;}