LeetCode 热题100之哈希

1.两数之和

思路分析1（暴力法）

• 双重循环枚举满足num[i] + nums[j] = = target的索引，刚开始不知道如何返回一对索引。后来知道可以直接通过return {i,j}返回索引；
• 注意：j应该从i+1处开始，避免使用两次相同的元素；
• 如果没有找到，则需要返回空return{};
• 时间复杂度：$o(N^2),$其中N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次；

具体实现代码（详解版）：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int l = nums.size(); // 获取数组的长度// 外层循环遍历数组中的每个元素for (int i = 0; i < l; i++) {// 内层循环从下一个元素开始遍历for (int j = i + 1; j < l; j++) {// 检查当前两个元素的和是否等于目标值if (nums[i] + nums[j] == target) {// 如果找到了，返回这两个元素的索引return {i, j};}}}// 如果没有找到满足条件的元素，返回空的 vectorreturn {};}
};

思路分析2（哈希表优化）

• 遍历数组：对每个元素 nums[i]，计算它的补数 target - nums[i];
• 查找补数：使用 hashtable.find() 方法检查补数是否已存在于哈希表中;
• 返回索引：如果找到了补数，就返回补数的索引和当前索引i;
• 更新哈希表：如果未找到补数，则将当前元素及其索引存入哈希表

样例模拟：

对于 nums = [2, 7, 11, 15] 和 target = 9，我们使用twoSum 函数来找到两个数的索引，使它们的和等于目标值。
1.第一轮迭代(i= 0)

• 当前元素 nums[0] = 2，补数为 9 - 2 = 7;
• 哈希表中没有 7，所以将 2 存入哈希表：hashtable[2] = 0;

2.第二轮迭代（i =1):

• 当前元素 nums[1] = 7，补数为 9 - 7 = 2。
• 在哈希表中找到 2，其索引为 0;
• 返回 {0, 1}，表示 nums[0] 和 nums[1] 的和等于 9。

具体实现代码（详解版）：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashtable; // 创建哈希表，存储数字及其索引// 遍历数组中的每个元素for (int i = 0; i < nums.size(); i++) {// 计算当前数字的补数int complement = target - nums[i];// 在哈希表中查找补数auto it = hashtable.find(complement);if (it != hashtable.end()) {// 如果找到了补数，返回其索引和当前索引return {it->second, i};}// 将当前数字及其索引存入哈希表hashtable[nums[i]] = i;}// 如果没有找到，返回空的 vectorreturn {};}
};

2.字母异位词分组

思路分析1（字母排序）

• 理解字母异位词：两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。
  
• 需要根据特征进行归类，就应该利用哈希表；
• 由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键，哈希表的值为一组字母异位词列表。
• • 哈希表：使用 unordered_map 来存储排序后的字符串作为键，原字符串作为值的列表。
• • 字符串排序：通过排序将字母异位词归为同一键。
• • 结果构造：将哈希表中的每个值（异位词组）添加到结果向量中。

具体实现代码（详解版):

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> mp; // 哈希表，存储异位词组// 遍历每个字符串for (string& str : strs) {string key = str; // 复制当前字符串sort(key.begin(), key.end()); // 将字符串排序，作为哈希表的键mp[key].push_back(str); // 将原字符串加入对应的组}vector<vector<string>> ans; // 存储结果for (auto it = mp.begin(); it != mp.end(); ++it) {ans.push_back(it->second); // 将每组异位词添加到结果中}return ans; // 返回结果}
};

复杂度分析：

• 时间复杂度：O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。

3.128最长连续序列

思路分析1（先排序，虽然不符合$O(n)$的时间复杂度吗，但是是最快的）

• 先对数组进行排序；
• 然后判断是否是连续序列
• • 如果差1，即是连续的数字，更新最长序列长度
• • 如果它们相等（重复），则可以忽略，不需要修改 mx
• 否则，说明当前数字与之前的连续序列断开了。需要重置当前序列长度 mx 为 1，因为当前数字本身可以视为新的序列的开始。

具体实现代码（详解版）

class Solution {
public:int longestConsecutive(vector<int>& nums) {if(nums.size() == 0) return 0; // 如果数组为空，返回 0int ans = 1, mx = 1; // 初始化最长序列长度和当前序列长度sort(nums.begin(), nums.end()); // 对数组进行排序for(int i = 1; i < nums.size(); i++) {if(nums[i - 1] + 1 == nums[i]) { // 如果是连续的数字ans = max(ans, ++mx); // 更新最长序列长度}else if(nums[i - 1] == nums[i]) { continue; // 跳过重复数字}else {mx = 1; // 重置当前序列长度}}return ans; // 返回最长连续序列的长度}
};

2.思路分析2：使用哈希集合（优化为$O(n)$)

• 使用 unordered_set 存储输入数组中的所有数字。这允许我们在 O(1) 的时间内快速查找任意数字。

• 通过 for 循环遍历 numSet 中的每个数字，检查它是否是一个潜在的连续序列的起点。

• 确定起始点：

  • 通过 numSet.find(num - 1) == numSet.end() 检查当前数字 num 是否是一个连续序列的起点。
  • 如果 num - 1 不在集合中，说明 num 是一个新的序列的开始。

• 查找连续序列

  • 如果 num 是起始数字，初始化 currentNum 为 num，并将 currentStreak 设为 1（表示当前序列的长度）。
  • 使用 while 循环，查找 currentNum + 1 是否存在于集合中。如果存在，则 currentNum 自增，并且 currentStreak 增加 1，直到没有连续的数字为止。

• 更新最长序列长度：在每次找到一个完整的连续序列后，将 longestStreak 更新为当前序列长度和已有最长序列长度的较大值。

• 最后，返回 longestStreak，即数组中最长连续序列的长度

具体实现代码（详解版）：

class Solution {
public:int longestConsecutive(vector<int>& nums) {// 使用 unordered_set 存储所有数字unordered_set<int> numSet(nums.begin(), nums.end());int longestStreak = 0;// 遍历每个数字for (int num : numSet) {// 只从未处理的起始数字开始查找//如果 num - 1 不在集合中，说明 num 是一个新的序列的开始。if (numSet.find(num - 1) == numSet.end()) {int currentNum = num;int currentStreak = 1;// 向上查找连续的数字while (numSet.find(currentNum + 1) != numSet.end()) {currentNum++;currentStreak++;}// 更新最长序列长度longestStreak = max(longestStreak, currentStreak);}}return longestStreak; // 返回最长连续序列的长度}
};

这是两种算法的通过时间，使用算法1的竟然还快一点~（hhhh）

总结：哈希表（集合）常常用于解决与查找、计数或分组相关的问题，在数据结构和算法中广泛应用，如实现字典、集合等。哈希表是一种高效且灵活的数据结构，适合于多种场景，尤其是当需要快速查找、插入和删除时。理解其原理和使用方式可以帮助解决许多实际问题。