【LeetCode 热题 100】哈希 系列

📁1. 两数之和

        本题就是将通过两层遍历优化而成的，为什么需要两层遍历，因为遍历 i 位置时，不知道i-1之前的元素是多少，如果我们知道了，就可以通过两数相加和target比较即可。

        因为本题要求返回下标，所以我们是用unordered_map来存储<元素值，下标>

vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int , int> hash;for(int i = 0 ; i < nums.size() ; ++i){if(hash.count(target - nums[i]))return {hash[target - nums[i]] , i};hash[nums[i]] = i;}return {-1 , -1};}

📁49. 字母异位词分组

        字母异位词 是由重新排列源单词的所有字母得到的一个新单词。我们就根据这个特性，将字符串重新排序，将重新排序后相同的字符串放到字符串数组中，最终这些字符串数组就是最终结果。

        这里我们就用到了unordeed_map<string , vector<string>> 来映射重新排序后的字符串对应的字符串数组。

vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string , vector<string>> hash;for(auto str : strs){string s = str;sort(s.begin() , s.end());hash[s].push_back(str);}vector<vector<string>> ret;for(auto kv : hash)ret.push_back(kv.second);return ret;
}

📁128. 最长连续序列

        找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度，是本题目的关键。如果仅仅通过一次遍历是不能解决问题的，因为遍历到 i 位置时，得到num[i+1]，但是num[i] - 1可能出现在i位置以后，因此我们需要排序或者记录下来元素是否出现过。

        题目要求时间复杂度是O(N)，因此不考虑排序，这里就用到哈希unordered_set来记录元素是否出现过。

        核心思想就是，判断每个元素是否是最长数字连续序列的第一个元素；如果是，查找之后是否有元素及之后元素的个数。如果不是，就不需要处理了。

int longestConsecutive(vector<int>& nums) {unordered_set<int> hash;for(auto e: nums)hash.insert(e);int ans = 0;for(auto& e : hash){if(!hash.count(e - 1)){int cur = e;int step = 1;while(hash.count(cur + 1)){cur += 1;step += 1;}ans = max(ans , step);}}return ans;}