哈希leetcode-1

2024-09-09 18:12

文章标签 leetcode 哈希

本文主要是介绍哈希leetcode-1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1前言

2.例题

2.1两数之和

2.2判断是否互为字符重排

2.3存在重复元素1

2.4存在重复元素2

2.5字母异位词分组

1前言

哈希表主要是适合于快速查找某个元素（O(1)）

当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n)

一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。

最简单的比如数组模拟字符存储，只要开26个char的数组即可。

用数组模拟速度比用容器哈希快。但是有局限性（主要是针对数据范围小的时候）

2.例题

2.1两数之和

1. 两数之和 - 力扣（LeetCode）

利用哈希表，存储当前位置数字前的所有数字。

这样可以直接查询需要的数字。
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n=nums.size();unordered_map<int,int>hash1;for(int i=0;i<n;i++){if(hash1.count(target-nums[i])){return {hash1[target-nums[i]],i};}hash1[nums[i]]=i;}return {};}
};
2.2判断是否互为字符重排

面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）

思路1

利用两个哈希表，一个存s1中字符出现个数，一个存s2中字符出现个数

然后比较两个哈希表即可

注意，这题是字符，所以直接用数组模拟即可。
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;int hash1[26]={0};int hash2[26]={0};//统计s1for(auto a:s1){hash1[a-97]++;}//统计s2for(auto a:s2){hash2[a-97]++;}//比较for(int i=0;i<26;i++){if(hash1[i]!=hash2[i])return false;}return true;}
};
思路2

区别不大。只用1个哈希表。遍历s2的时候，同步更新
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;int hash1[26]={0};for(auto a:s1){hash1[a-97]++;}for(auto a:s2){hash1[a-97]--;if(hash1[a-97]<0)return false;} //比较神奇的是，如果加上这段for循坏，能过且0ms，但是如果不加，4ms能过for(int i=0;i<26;i++){if(hash1[i]>0)return false;}return true;}
};
2.3存在重复元素1

217. 存在重复元素 - 力扣（LeetCode）

哈希表统计数字出现即可。
class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int,int>hash1;for(auto s:nums){hash1[s]++;if(hash1[s]>=2)return true;}return false;}
};
2.4存在重复元素2

219. 存在重复元素 II - 力扣（LeetCode）

直接用哈希表判断即可
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,int>hash1;int n=nums.size();for(int i=0;i<n;i++){if(hash1.count(nums[i])){if(i-hash1[nums[i]]<=k)return true;}hash1[nums[i]]=i;}return false;}
};
2.5字母异位词分组

49. 字母异位词分组 - 力扣（LeetCode）

思路就是利用排序，统计是否是异位词
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>>hash1;for(auto x:strs){auto tmp=x;sort(tmp.begin(),tmp.end());hash1[tmp].push_back(x);}vector<vector<string>>ret(0);for(auto x:hash1){ret.push_back(x.second);}return ret;}
};