LeetCode | 哈希表 - HaoyangPing

分类：哈希表 / 总结

讲解#

哈希表题目的核心是：先建一张表，再去表里查东西。

两数之和把 已经遍历过的数字，以及它的下标放进字典作为哈希表,查target - num 在不在表里，最后返回两个数字对应的下标。

字母异位词分组把 排序后的字符串(key) -> 原字符串列表(value)放进字典作为哈希表,,查当前字符串排序后的 key在不在表里，最后返回字典里所有 value，也就是分好组的字符串列表。

最长连续序列把 nums 通过set(nums)去重后的所有数字放进集合作为哈希表,查先查 x - 1 在不在确定是不是序列起点，再不断查 x + 1、x + 2、…在不在表里，最后返回最长连续序列的长度。

哈希表题目重要是：我应该把什么变成 key，又要用这个 key 查什么。

代码#

两数之和#

1
class Solution:
2
    def twoSum(self, nums: list[int], target: int) -> list[int]:
3
        seen = {}
4

5
        for i, num in enumerate(nums):
6
            need = target - num
7
            if need in seen:
8
                return [seen[need], i]
9

10
            seen[num] = i
11
        return []

字母异位词分组（排序法）#

1
from collections import defaultdict
2
from typing import List
3

4

5
class Solution:
6
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
7
        mp = defaultdict(list)
8

9
        for st in strs:
10
            key = "".join(sorted(st))
11
            mp[key].append(st)
12

13
        return list(mp.values())

最长连续序列#

1
from typing import List
2

3

4
class Solution:
5
    def longestConsecutive(self, nums: List[int]) -> int:
6
        st = set(nums)
7
        m = len(st)
8

9
        ans = 0
10
        for x in st:
11
            if x - 1 in st:
12
                continue
13

14
            y = x + 1
15
            while y in st:
16
                y += 1
17

18
            ans = max(ans, y - x)
19
            if ans * 2 >= m:
20
                break
21

22
        return ans

参考资料#

两数之和
字母异位词分组
最长连续序列
LeetCode 两数之和：https://leetcode.com/problems/two-sum/
LeetCode 字母异位词分组：https://leetcode.com/problems/group-anagrams/
LeetCode 最长连续序列：https://leetcode.com/problems/longest-consecutive-sequence/
力扣两数之和题解：https://leetcode.cn/problems/two-sum/solutions/
力扣字母异位词分组题解：https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solution/
力扣最长连续序列题解：https://leetcode.cn/problems/longest-consecutive-sequence/solutions/3005726/ha-xi-biao-on-zuo-fa-pythonjavacgojsrust-whop/

音乐

音乐

讲解#

代码#

两数之和#

字母异位词分组（排序法）#

最长连续序列#

参考资料#

文章分享

评论区

音乐

文章目录