1. 哈希

约 1342 字大约 4 分钟

LeetcodePythonC++

2025-08-30

LeetCode 热题 100

1.1 两数之和

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]
提示
思路：用一个哈希表来存储遍历过的元素，后续遍历如果需要的值在哈希表中有，那么就查找到了。
Python
```
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    idx = {}
    for i, num in enumerate(nums):
        if target - num in idx:
            return [idx[target - num], i]
        idx[num] = i
```
C++
```
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> idx;
        for (int j = 0; ; j++) {
            auto it = idx.find(target - nums[j]);
            // 这里的 auto 是：unordered_map<int, int>::iterator
            if (it != idx.end()) {
                return {it->second, j};
            }
            idx[nums[j]] = j;
        }
    }
};
```
C++的 map 和 unordered_map
- map内部是红黑树，元素按键有序存储。查找、插入、删除都需要沿树查找路径，复杂度约为 log n。
- unordered_map内部是哈希表，根据键的哈希值直接定位到桶(bucket)。平均情况下查找是常数时间 O(1)。
时间复杂度： $O(n)$ 。
空间复杂度： $O(n)$ 。

1.2 字母异位词分组

49. 字母异位词分组
给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
示例 1：
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
- 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
- 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
- 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
示例 2：
输入: strs = [""]
输出: [[""]]
示例 3：
输入: strs = ["a"]
输出: [["a"]]
提示
思路：一开始想过用Counter，可以区分出不同的字符串是否是一组字母异位词，但是仍然需要花费额外的时间去判断当前字符串是属于哪一组的字母异位词。因此改用sorted，排序后的字符串天然拥有唯一性，适合搭配哈希表来使用，key表示排序后的字符串，value使用一个列表来整合这组的字母异位词。
Python
```
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    from collections import defaultdict
    dic = defaultdict(list)
    for s in strs: # O(n)
        sorted_s = ''.join(sorted(s)) # O(mlogm)
        dic[sorted_s].append(s)
    return list(dic.values())
```
C++
```
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string s : strs) {
            string sorted_s = s;
            ranges::sort(sorted_s);
            mp[sorted_s].push_back(s);
        }
        vector<vector<string>> res;
        for (auto [_, value] : mp) {
            res.push_back(value);
        }
        return res;
    }
};
```
时间复杂度： $O(nmlogm)$ 。其中 n 为 strs 的长度，m 为 strs[i] 的长度。每个字符串排序需要 $O(mlogm)$ 的时间，有 n 个字符串，所以总的时间复杂度为 $O(nmlogm)$ 。
空间复杂度： $O(nm)$ 。

1.3 最长连续序列

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
示例 3：
输入：nums = [1,0,1,2]
输出：3
提示
思路：set拥有去除重复元素的功能，因此将nums放入哈希集合，此时注意如果2,3,4是连续的，那么1,2,3,4必然连续，因此如果遇到当前元素-1也在集合内部，避免重复计算直接跳过即可。
Python
```
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
    st = set(nums)
    res = 0
    for x in st:
        if x - 1 in st:
            continue
        y = x + 1
        while y in st:
            y += 1
        res = max(res, y - x)
    return res
```
C++
```
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int res = 0;
        for (int x : st) {
            if (st.contains(x - 1)) {
                continue;
            }
            int y = x + 1;
            while (st.contains(y)) {
                y++;
            }
            res = max(res, y - x);
        }
        return res;
    }
};
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(m)$ 。其中 m 是 nums 中的不同元素个数。
C++中的 unordered_set 和 unordered_map
- unordered_set<Key>，只存「键」，类似于哈希版集合{1, 2, 3}，用于判断某个元素是否存在。
- unordered_map<Key, Value>，存「键 → 值」映射，哈希版字典{1: "one", 2: "two"}，通过 key 查找对应 value。
- 相同点：底层都使用哈希表（hash table）实现，查找复杂度平均 O(1)，最坏 O(n)，元素无序存储，key 唯一（不允许重复）。