hot100哈希题解

发表于 2025/01/15 更新于 2025/01/15

作者 匆匆那年 13 分钟阅读

1. 两数之和

问题描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

$2 <= nums.length <= 10^4$
$-10^9 <= nums[i] <= 10^9$
$-10^9 <= target <= 10^9$
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

题解

以下是 两数之和 的 C++ 解法，利用哈希表可以将时间复杂度优化到 $O(n)$。

解题思路

遍历数组的同时，使用一个哈希表记录已经访问过的元素及其下标。
对于每个元素，计算其与目标值的差值 complement = target - nums[i]。
检查哈希表中是否存在这个差值：
- 如果存在，返回差值对应的下标和当前元素的下标。
- 如果不存在，将当前元素和其下标加入哈希表。
遍历结束时，必然可以找到答案（因为题目保证有解）。

C++ 代码实现

  
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hashMap; // 用于存储值和下标的哈希表

    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i]; // 计算差值
        // 检查差值是否在哈希表中
        if (hashMap.find(complement) != hashMap.end()) {
            return {hashMap[complement], i}; // 找到解并返回
        }
        // 如果未找到，记录当前值和下标
        hashMap[nums[i]] = i;
    }

    return {}; // 题目保证有解，不会到这里
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    vector<int> result = twoSum(nums, target);

    cout << "[" << result[0] << ", " << result[1] << "]" << endl;

    return 0;
}

代码解析

哈希表的作用：
- 存储元素值和对应下标，便于快速查找元素是否已存在，查找的时间复杂度为 $O(1)$。
时间复杂度：
- 哈希表插入和查找操作的均摊时间复杂度为 $O(1)$。
- 因此整体时间复杂度为 $O(n)$，其中 $n$ 为数组长度。
空间复杂度：
- 哈希表的空间复杂度为 $O(n)$，因为最多存储 $n$ 个元素。

示例运行

输入：

  
nums = [2, 7, 11, 15], target = 9

输出：

[0, 1]

此代码解决了问题并满足进阶要求的时间复杂度 O(n)O(n)。

49. 字母异位词分组

问题描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

$1 <= strs.length <= 10^4$
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

题解

以下是 字母异位词分组 的 C++ 解法，利用哈希表和排序可以高效解决问题。

解题思路

定义异位词：
- 如果两个单词是异位词，对其排序后结果相同。例如，eat 和 tea 排序后均为 aet。
哈希表的作用：
- 使用一个哈希表 unordered_map<string, vector<string>>，键为排序后的字符串，值为对应的单词列表。
具体步骤：
- 遍历字符串数组，对每个字符串进行排序，作为哈希表的键。
- 将未排序的字符串插入到对应键的值列表中。
- 遍历完成后，哈希表的值即为分组结果。

C++ 代码实现

  
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> hashMap; // 哈希表：键为排序后的字符串，值为异位词组

    for (const string& str : strs) {
        string sortedStr = str; // 创建一个副本用于排序
        sort(sortedStr.begin(), sortedStr.end()); // 排序字符串
        hashMap[sortedStr].push_back(str); // 将原字符串加入对应组
    }

    // 提取哈希表中的所有值
    vector<vector<string>> result;
    for (const auto& pair : hashMap) {
        result.push_back(pair.second);
    }

    return result;
}

int main() {
    vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
    
    vector<vector<string>> result = groupAnagrams(strs);

    // 输出结果
    for (const auto& group : result) {
        cout << "[";
        for (const auto& word : group) {
            cout << word << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

代码解析

排序确定异位词归属：
- 字符串排序后，异位词具有相同的排序结果，因此排序结果可作为分组的键。
哈希表存储：
- 键为排序后的字符串，值为与其对应的异位词列表。
提取结果：
- 遍历哈希表，将所有值（即分组）存入结果数组。

时间复杂度

字符串排序：
- 假设字符串的平均长度为 $k$，每次排序的时间复杂度为 $O(k \log k)$。
- 遍历整个数组需要 $O(n \cdot k \log k)$，其中 $n$ 为字符串数组的长度。
插入哈希表：
- 插入哈希表的均摊时间复杂度为 $O(1)$，总体为 $O(n)$。
整体复杂度：
- $O(n \cdot k \log k)$。

空间复杂度

哈希表存储：
- 哈希表存储所有字符串及其分组，空间复杂度为 $O(n \cdot k)$。
排序的临时空间：
- 每次排序的临时空间复杂度为 $O(k)$，总空间复杂度为 $O(n \cdot k)$。

示例运行

输入：

  
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出：

[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

此代码通过高效的哈希表和排序方法，解决了字母异位词分组问题。

128. 最长连续序列

问题描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

$0 <= nums.length <= 10^5$
$-10^9 <= nums[i] <= 10^9$

题解

以下是 最长连续序列 的 C++ 解法，采用哈希表来实现 $O(n)$ 的时间复杂度。

解题思路

利用哈希集合去重和快速查询：
- 将数组中的所有元素存入哈希集合 unordered_set 中，去重且便于快速查询。
寻找序列起点：
- 遍历哈希集合中的每个元素，判断该元素是否是一个序列的起点（即：num - 1 不存在于集合中）。
扩展序列：
- 如果当前元素是序列起点，向后扩展序列，直到找不到连续的数字为止，记录序列长度。
记录最大长度：
- 每次扩展序列后，更新最长长度。

C++ 代码实现

  
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end()); // 使用哈希集合存储所有数字
    int longestStreak = 0;

    for (const int& num : numSet) {
        // 只有当当前数字是序列的起点时，才开始计算序列长度
        if (!numSet.count(num - 1)) {
            int currentNum = num;
            int currentStreak = 1;

            // 向后扩展序列
            while (numSet.count(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            // 更新最长序列长度
            longestStreak = max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << "Longest Consecutive Sequence Length: " << longestConsecutive(nums) << endl;
    return 0;
}

代码解析

哈希集合去重：
- 将数组中的所有数字插入 unordered_set，去重且可以 $O(1)$ 时间复杂度查询是否存在某数字。
判断序列起点：
- 只有当 num - 1 不在集合中时，才认为当前数字是序列的起点。
扩展序列：
- 使用 while 循环向后检查是否有连续的数字，记录当前序列的长度。
更新最长长度：
- 每次扩展结束后，将当前序列长度与记录的最大长度比较，更新最长长度。

时间复杂度

哈希集合构建：
- 插入所有数字到集合需要 $O(n)$。
遍历集合：
- 每个数字最多被访问两次（一次作为起点，一次在扩展时），因此总复杂度为 $O(n)$。

总时间复杂度： $O(n)$。

空间复杂度

主要消耗在哈希集合，空间复杂度为 $O(n)$。

示例运行

输入：

  
nums = [100, 4, 200, 1, 3, 2]

输出：

4

总结

此算法利用哈希集合的特性，有效减少了冗余操作，实现了线性时间复杂度 $O(n)$。

leetcode, hot100

本文由作者按照 CC BY 4.0 进行授权

1. 两数之和

问题描述

题解

解题思路

C++ 代码实现

代码解析

示例运行

49. 字母异位词分组

问题描述

题解

解题思路

C++ 代码实现

代码解析

时间复杂度

空间复杂度

示例运行

128. 最长连续序列

问题描述

题解

解题思路

C++ 代码实现

代码解析

时间复杂度

空间复杂度

示例运行

总结

热门标签