当前位置：首页 > article >正文

LeetCode 热题100之哈希

article 2024/10/26 22:01:06

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};
                }
            }
        }
        // 如果没有找到满足条件的元素，返回空的 vector
        return {};
    }
};

思路分析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;
        }
        // 如果没有找到，返回空的 vector
        return {};
    }
};

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; // 如果数组为空，返回 0
        
        int 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; // 返回最长连续序列的长度
    }
};