LeetCode Hot 100 | 哈希表专题（C++ 题解）

LeetCode Hot 100 | 哈希表专题（C++ 题解）

哈希表这块内容，说难不难，说简单也不简单。用好了，O(n) 秒杀；没想到，卡在暴力 O(n²) 出不来。Hot 100 里哈希表共 6 道题，今天一起整理一遍，把套路摸清楚。

1. Two Sum（两数之和）🟢 简单

题目简介

给定一个整数数组nums和一个目标值target，找出数组中两个数之和等于target的下标。

解题思路

暴力做法是双层循环，O(n²)，没啥意思。

用哈希表的思路是：遍历数组，对于每个nums[i]，先查表里有没有target - nums[i]。有的话直接返回；没有的话，把nums[i]存进去。一次遍历搞定。

关键点：先查后存，避免自己跟自己配对。

代码

classSolution{public:vector<int>twoSum(vector<int>&nums,inttarget){unordered_map<int,int>umap;for(inti=0;i<nums.size();i++){if(umap.count(target-nums[i]))return{i,umap[target-nums[i]]};elseumap[nums[i]]=i;}return{0,0};}};

复杂度

• 时间复杂度：O(n)，一次遍历
• 空间复杂度：O(n)，哈希表最多存 n 个元素

2. Group Anagrams（字母异位词分组）🟡 中等

题目简介

给一个字符串数组，把所有字母异位词（组成字母相同、排列不同的词）分到同一组，返回分组结果。

解题思路

核心问题是：怎么判断两个字符串是异位词？

常规思路是排序后作为 key，但这里用了更巧的方法：用一个长度为 26 的array<int, 26>记录每个字母的出现次数，作为哈希表的 key。

由于std::unordered_map默认不支持array作为 key，需要自定义哈希函数。代码里用了 lambda + XOR 累积的方式实现。

代码

classSolution{public:vector<vector<string>>groupAnagrams(vector<string>&strs){autohashArray=[fn=hash<int>{}](constarray<int,26>&arr){returnaccumulate(arr.begin(),arr.end(),0,[&](intacc,intnum){return(acc<<1)^fn(num);});};unordered_map<array<int,26>,vector<string>,decltype(hashArray)>umaps(0,hashArray);array<int,26>arr;for(constautostr:strs){arr={0};for(constautoc:str){arr[c-'a']++;}umaps[arr].emplace_back(move(str));}vector<vector<string>>ans;for(automap:umaps){ans.emplace_back(map.second);}returnans;}};

复杂度

• 时间复杂度：O(n·m)，n 是字符串数量，m 是字符串平均长度
• 空间复杂度：O(n·m)，存储所有字符串

3. Longest Consecutive Sequence（最长连续序列）🟡 中等

题目简介

给一个未排序的整数数组，找出数字连续的最长序列（不要求下标连续），要求时间复杂度 O(n)。

解题思路

先把所有数字扔进unordered_set，O(1) 查询。

然后遍历 set，对于每个数num，只有当num - 1不在set 里时，才开始计数（说明这是序列的起点）。然后一路向右数，直到断掉。

这样每个数最多被访问两次（一次判断是不是起点，一次被序列扫过），整体 O(n)。

代码

classSolution{public:intlongestConsecutive(vector<int>&nums){unordered_set<int>uset;intans=0;for(autonum:nums){uset.insert(num);}for(autonum:uset){if(!uset.count(num-1)){intval=num;inttmp_len=1;while(uset.count(++val)){tmp_len++;}ans=max(ans,tmp_len);}}returnans;}};

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

4. Longest Substring Without Repeating Characters（无重复字符的最长子串）🟡 中等

题目简介

给一个字符串，找出其中不含重复字符的最长子串的长度。

解题思路

滑动窗口经典题。用双指针left和right，维护一个窗口内字符频率的哈希表。

right每往右一步，把新字符加入 map。如果新字符频率超过 1，说明有重复，就一直收缩左边left，直到窗口内没有重复字符为止。

每次更新答案。

代码

classSolution{public:intlengthOfLongestSubstring(string s){unordered_map<int,int>umap;intleft=0;intans=0;for(intright=0;right<s.size();right++){umap[s[right]]++;while(umap[s[right]]>1){umap[s[left]]--;left++;}ans=max(ans,right-left+1);}returnans;}};

复杂度

• 时间复杂度：O(n)，每个字符最多进出窗口各一次
• 空间复杂度：O(min(n, Σ))，Σ 是字符集大小（ASCII 最多 128）

5. Find All Anagrams in a String（找到字符串中所有字母异位词）🟡 中等

题目简介

给两个字符串s和p，找出s中所有p的字母异位词的起始索引。

解题思路

和上一题类似，还是滑动窗口。先把p中每个字符的频率存到cnt数组，然后遍历s，每次把s[right]对应的计数减 1。

如果计数减到负数，说明当前字符在窗口里超出了p的需求，就收缩左边。

当窗口长度恰好等于p.size()时，说明找到了一个异位词，记录起始位置。

代码

classSolution{public:vector<int>findAnagrams(string s,string p){array<int,26>cnt={0};vector<int>ans;for(autoc:p)cnt[c-'a']++;intleft=0;for(intright=0;right<s.size();right++){cnt[s[right]-'a']--;while(cnt[s[right]-'a']<0){cnt[s[left]-'a']++;left++;}if(right-left+1==(int)p.size())ans.push_back(left);}returnans;}};

复杂度

• 时间复杂度：O(n)，n 是字符串s的长度
• 空间复杂度：O(1)，固定大小的 26 位计数数组

6. Subarray Sum Equals K（和为 K 的子数组）🟡 中等

题目简介

给一个整数数组和一个整数k，统计和为k的连续子数组的数目。

解题思路

前缀和 + 哈希表，这道题的经典打法。

定义s[i]为前 i 个元素的前缀和。子数组[j+1, i]的和为s[i] - s[j]。

我们要找s[i] - s[j] == k，即s[j] == s[i] - k。

用哈希表cnt存已经出现过的前缀和及其次数。初始化cnt[0] = 1（空前缀）。每遍历到位置 i，查cnt[s - k]，加到答案里，再把s存入cnt。

代码

classSolution{public:intsubarraySum(vector<int>&nums,intk){unordered_map<int,int>cnt{{0,1}};ints=0;intans=0;for(inti=0;i<nums.size();i++){s+=nums[i];if(cnt.contains(s-k))ans+=cnt[s-k];cnt[s]++;}returnans;}};

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)，哈希表存前缀和

总结

哈希表的本质是用空间换时间，把查询从 O(n) 降到 O(1)。配合滑动窗口和前缀和，能解决大量线性扫描问题。这 6 道题把常见套路基本覆盖了，多刷几遍，形成肌肉记忆，面试遇到类似题直接秒。

如果有问题欢迎评论区交流，我们下篇见 👋