Leetcode Hot 100 —— 哈希

1. 两数之和思路与解法当遍历到某一元素时比如3当要求两数之和为9时需要看6在之前有没有出现过也就是某元素是否出现在这个集合中那么我们就应该想到使用哈希法了。因为本题我们不仅要知道元素有没有遍历过还要知道这个元素对应的下标需要使用 key、value结构来存放key来存元素value来存下标那么使用map正合适。这道题目中并不需要key有序选择std::unordered_map 效率更高map的目的是用来存放我们访问过的元素因为遍历数组的时候需要记录我们之前遍历过哪些元素和对应的下标这样才能找到与当前元素相匹配的即相加等于target。map中key和value分别表示什么在map里key键用来查找本题为元素的值value值表示这个键对应的数据本题为元素对应的索引这道题我们需要给出一个元素判断这个元素是否出现过如果出现过返回这个元素的下标。那么判断元素是否出现这个元素的值就作为key因为map的作用是最快地查找key是否在map中出现过。所以数组中的元素作为key有key对应的就是valuevalue用来存下标。所以map中的存储结构为 {key数据元素value数组元素对应的下标}。在遍历数组的时候只需要向map去查询是否有和目前遍历元素匹配的数值如果有就找到了匹配对如果没有就把目前遍历的元素放进map中因为map存放的就是我们访问过的元素。整体思路定义unordered_map——寻找找到返回未找到就添加——最终没有匹配的返回空classSolution{public:vectorinttwoSum(vectorintnums,inttarget){unordered_mapint,intmap;for(inti0;inums.size();i){autoitmap.find(target-nums[i]);if(it!map.end()){return{it-second,i};}//必须放在这里不能放在前面要查找之后再插入避免与自身配对map.insert({nums[i],i});//map.insert(pairint, int(nums[i], i));}return{};}};【注】1、map.find(…)unordered_map 的成员函数用于查找指定的键参数是要查找的键key返回一个迭代器pairconst Key, Value 类型2、unordered_map 是一个键值对key-value pair容器它存储的元素实际上是pairconst Key, Value 类型的对象。用map.insert({nums[i], i}); 更简洁3、如果代码开头有using namespace std则不需要加 std::leetcode平台模板通常包含 using namespace std。4、为何return {iter-second, i}因为要求返回的是满足条件的两个元素的数组下标即valueiter-firstfirst访问的是 pairconst Key, Value 中的 Key 部分存放数组中的元素值iter-secondsecond 访问的是 pairconst Key, Value 中的 Value 部分存放索引map.insert({nums[i],i});添加时是将当前元素的键值加入ACM#includebits/stdc.husingnamespacestd;classSolution{public:vectorinttwoSum(vectorintnums,inttarget){unordered_mapint,intmap;for(inti0;inums.size();i){autoitmap.find(target-nums[i]);if(it!map.end()){return{it-second,i};}map.insert({nums[i],i});}return{};}};intmain(){intn,target;cinntarget;vectorintnums(n);for(inti0;in;i){cinnums[i];}Solution solution;vectorintresultsolution.twoSum(nums,target);coutresult[0] result[1]endl;return0;}49. 字母异或词分组思路及解法字母异位词的特点是它们的字母组成相同只是排列顺序不同。因此可以通过对每个字符串进行排序按从小到大的顺序排列将排序后的字符串作为键将原始字符串作为值存入哈希表中。最后将哈希表中的值提取出来即为分组后的结果。核心代码classSolution{public:vectorvectorstringgroupAnagrams(vectorstringstrs){unordered_mapstring,vectorstringmap;for(stringstr:strs){string keystr;//复制一个key出来再排序避免影响原字符串str!!sort(key.begin(),key.end());map[key].push_back(str);}vectorvectorstringresult;for(autoitmap.begin();it!map.end();it){result.push_back(it-second);//将哈希map的值输出即为结果}returnresult;}};思路定义哈希map——取输入的每个字符串复制后排序作为键原字符串作为值存入哈希map——从哈希map中取值即为结果【注】1、这里都是string。别写成int了哈希map例子mp[“aet”] [“eat”, “tea”, “ate”]键aetstring类型对应的值为eat, “tea”, “ate”vectorstring类型因此map为string,vectorstring类型2、operator[ ] 会自动创建默认值3、emplace_back是C容器里的一个尾部插入函数是把构造对象需要的参数直接传进去让容器在尾部原地构造。和push_back的区别push_back是把一个已经存在的对象塞进去。什么情况下emplace_back更有优势当元素类型比较复杂时更明显。比如vectorpairint,stringv;v.emplace_back(1,abc);如果用 push_back通常要写v.push_back(pairint,string(1,abc));或者常用干脆统一用这个v.push_back({1,abc});ACM:#includebits/stdc.husingnamespacestd;classSolution{public:vectorvectorstringgroupAnagrams(vectorstringstrs){unordered_mapstring,vectorstringmap;for(stringstr:strs){string keystr;sort(key.begin(),key.end());map[key].push_back(str);}vectorvectorstringresult;for(autoitmap.begin();it!map.end();it){result.push_back(it-second);}returnresult;}};intmain(){intn;cinn;vectorstringstr(n);for(inti0;in;i){cinstr[i];}Solution solution;vectorvectorstringresultsolution.groupAnagrams(str);for(autoi:result){for(autoj:i){coutj ;}coutendl;}return0;}【注】1、这种写法每一行最后一个字符串后面也会输出一个空格。这样就不会for(autogroup:result){for(inti0;igroup.size();i){coutgroup[i];if(i!group.size()-1)cout ;}coutendl;}把结果长什么样写出来更直观例如先取i就是一个字符串数组如mp[“aet”]再取元素j才是字符串128.最长连续序列思路与解法核心思想就两步1、先把所有数字放进哈希集合 unordered_set会自动去重2、判断哈希集合中 num - 1 是否存在不存在说明num 是一个起点一定要从起点开始然后不断查num 1、num 2、num 3是否存在统计这一段连续长度核心代码classSolution{public:intlongestConsecutive(vectorintnums){if(nums.empty())return0;unordered_setintset(nums.begin(),nums.end());intlongestLength0;for(intn:nums){if(set.find(n-1)set.end()){intcurrentNumn;intcurrentLength1;while(set.find(currentNum1)!set.end()){currentNum;currentLength;}longestLengthlongestLengthcurrentLength?currentLength:longestLength;}}returnlongestLength;}};【注】1、longestLength longestLengthcurrentLength?currentLength:longestLength;要写在if(set.find(n-1)set.end()){}循环里#includeiostream#includeunordered_set#includevectorusingnamespacestd;classSolution{public:intlongestConsecutive(vectorintnums){if(nums.empty())return0;unordered_setintset(nums.begin(),nums.end());intlongestLength0;for(intn:set){if(set.find(n-1)set.end()){intcurrentNumn;intcurrentLength1;while(set.find(currentNum1)!set.end()){currentNum;currentLength;}longestLengthlongestLengthcurrentLength?currentLength:longestLength;}}returnlongestLength;}};intmain(){intn;cinn;vectorintres(n);for(inti0;in;i){cinres[i];}Solution solution;coutsolution.longestConsecutive(res)endl;return0;}【注】1、for(int n:set){注意是从set中取