算法刷题-哈希表
算法刷题-哈希表
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 < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
思路
先将nums1和nums2所有可能得到的值的组合存到哈希表中
在遍历nums3和nums4，判断0-nums3[i]-nums4[j]在不在哈希表中
时间复杂度为
代码
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 < na、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;
}