网站的交互怎么做,上海什么公司最有名,特色个人网站,建立网站怎么做文章目录 两数之和判定是否互为字符重排存在重复元素存在重复元素 II字母异位词分组 哈希表#xff1a;一种存储数据的容器#xff1b; 可以快速查找某个元素#xff0c;时间复杂度O(1)#xff1b; 当频繁查找某一个数时#xff0c;我们可以使用哈希表 创建一个容器#… 文章目录 两数之和判定是否互为字符重排存在重复元素存在重复元素 II字母异位词分组 哈希表一种存储数据的容器 可以快速查找某个元素时间复杂度O(1) 当频繁查找某一个数时我们可以使用哈希表 创建一个容器unordered_map用数组模拟一个简易哈希表 容器
数据结构unordered_mapmapunorded_setset实现机理hashRBThashRBT元素格式keyvaluekeyvaluekeykey存储规律无序键升序无序键升序元素重复键不可,值可键不可,值可不可重复不可重复
两数之和 题目两数之和 思路
暴力枚举初始两个指针 i,j遍历所有二元组判断nums[i] nums[j] target时间复杂度O(N^2)暴力枚举时间复杂度较高的原因是寻找 target - x 的时间复杂度过高使用哈希表我们可以将查找的时间复杂度降为O(1)对于每一个 x我们首先查询哈希表中是否存在target - x
我们可以将元素放入到哈希表中的同时检查表中是否已经存在当前元素所对应的目标元素这样就可以避免将元素全部放入到哈希表之后再来二次遍历
C代码
class Solution
{
public:vectorint twoSum(vectorint numbers, int target) {unordered_mapint, int hash; // 【数下标】for(int i 0; i numbers.size(); i){if(hash.find(target - numbers[i]) ! hash.end())return {i, hash[target - numbers[i]]};hash[ numbers[i] ] i;}return {};}
};判定是否互为字符重排 题目判定是否互为字符重排 思路
如果两长度不相等直接返回fasle创建一个hash表对于s1我们添加到hash表中对于s2中的每个字符如果hash中存在那么我们删除一个最后单独遍历一遍hash表如果其值不等于零也就意味值s1或s2中元素数量不匹配也就不发重排。
C代码
class Solution
{
public:bool CheckPermutation(string s1, string s2) {if(s1.size() ! s2.size()) return false;unordered_mapchar, int hash;for(auto ch : s1) hash[ch];for(auto ch : s2) hash[ch]--;for(auto x : hash) if(x.second ! 0)return false;return true;}};存在重复元素 题目存在重复元素 思路
创建一个hash表插入元素遍历hash表如果某个元素个数不等于1返回true遍历完后如果没有返回则返回false
C代码
class Solution
{
public:bool containsDuplicate(vectorint nums) {unordered_mapint, int hash;for(auto x : nums)hash[x];for(auto x : hash)if(x.second ! 1) return true;return false;}
};存在重复元素 II 题目存在重复元素 II 思路
和两数之和一样只需在遇到相同元素时相减判断
C代码
class Solution
{
public:bool containsNearbyDuplicate(vectorint nums, int k) {// 【数下标】unordered_mapint, int hash;int n nums.size();for(int i 0; i n; i){// 如果当前元素已经在 hash 中存在if(hash.count(nums[i])){// 判断下标是否满足要求if(i - hash[nums[i]] k)return true;}hash[nums[i]] i;}return false; // 遍历完数组没有发现符合条件的重复元素返回 false}
};字母异位词分组 题目 字母异位词分组 思路
判断两个字符串是否为字母异位词排序unordered_mapstring, vectorstring hash;
C代码
class Solution
{
public:vectorvectorstring groupAnagrams(vectorstring strs){unordered_mapstring, vectorstring hash;for(auto s : strs){string tmp s;sort(tmp.begin(), tmp.end());hash[tmp].push_bacck(s);}vectorvectorstring ret;for(auto [k, v] : hash){ret.push_bacck(y);} return ret;}
};
