LeetCode刷题笔记

此篇为Hot100刷题笔记(Python版)，持续更新中

底层认知

1. 算法评判基础：复杂度分析

  • 时间复杂度 (Time Complexity)：衡量算法运行速度随数据规模 $n$ 增大的增长趋势。
  • 空间复杂度 (Space Complexity)：衡量算法运行所需额外内存随数据规模 $n$ 增大的增长趋势。
  • 大 O 符号 (Big O Notation)：忽略常数项和低阶项，只保留最高阶项。
    • 示例：精确操作次数为 $\frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n$，化简后时间复杂度为 $O(n^2)$。
  • 常见复杂度等级 (从快到慢)：$O(1)$ > $O(\log n)$ > $O(n)$ > $O(n \log n)$ > $O(n^2)$

    核心策略：空间换时间
    现代计算机内存充裕，面对海量数据时，通常优先优化时间复杂度（如使用哈希表），通过消耗额外空间换取极速查询。

2. LeetCode 平台机制 (OJ 原理)

LeetCode 后台是一个测试引擎。它会自动导入你写的 Solution 类，实例化对象，并将成百上千组测试用例循环传入你的核心函数，最后比对你的 return 结果。因此，刷题时无需编写文件读取或 print 等外围代码，100% 专注算法逻辑本身即可。

哈希表 (Hash Table)

1. 概念

本质：本质就是python字典（只不过是先有哈希表再有字典）。

查询语法：if X in dict:。注意：in 关键字只搜索字典的“键 (Key)”，绝不会搜索“值 (Value)”。

可哈希性 (谁能当字典的键？)
字典的底层逻辑要求键必须拥有固定不变的指纹。

数据类型 能否当字典的键 为什么？
字符串 (String) / 数字 能 不可变，内容定死，指纹永远不变。
元组 (Tuple) 能 不可变，不能增删改，指纹永远不变。
列表 (List) / 字典 不能 可变，一旦内容被 append 或修改，哈希指纹改变，会导致找不到数据报错。

2. 使用函数

  • enumerate(iterable, start=0) (自动发号机)

    在遍历时同时提取“索引”和“值”，避免使用丑陋的 range(len())。

    1
    2
    for i, num in enumerate(nums):
        # i 是索引，num 是数值

  • 字符串重组

    sorted(str) 会返回一个列表（不能做键）。必须化零为整：

    1
    2
    key = "".join(sorted("tea")) # 用空字符胶水粘合成不可变字符串 "aet"
    # 或者转为元组: key = tuple(sorted("tea"))

  • collections.defaultdict(list) (自带兜底的字典)

    向不存在的键追加元素时自动创建空列表 []，省去繁琐的 if key not in dict: 判断。

  • dict.values() (提取字典里的所有值)

    返回字典中所有值组成的视图对象，常配合 list() 转成列表。

    1
    groups = list(mp.values())

  • set(iterable) (集合去重)

    将可迭代对象转换为集合，自动去重，并支持平均 $O(1)$ 的存在性查询。

    1
    num_set = set(nums)

  • max(a, b) (取最大值)

    返回多个值中的最大值，常用于维护历史最优答案。

    1
    longest_streak = max(longest_streak, current_streak)

3. 题目

题目 1：两数之和 (LeetCode 1)

原题

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

  • 示例: 输入: nums = [2,7,11,15], target = 9 -> 输出: [0,1]

答案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = {} # 格式：{数值: 索引}
        for i, num in enumerate(nums):
            # 1. 计算需要的同伙数值
            complement = target - num
            # 2. 查哈希表：同伙是否已经登记过？
            if complement in hashtable:
                return [hashtable[complement], i]
            # 3. 没找到：把自己登记到小本本上，供后续数字匹配
            hashtable[num] = i
        return []

解析

  • 核心逻辑：边遍历，边查找，边登记。
  • 为什么用哈希表：我们需要频繁地“回头寻找”某个特定的数字是否出现过。哈希表可以将这种查找的时间复杂度从 $O(n)$ 降到 $O(1)$。
  • 巧妙之处：“先查字典，后存自己”。这种执行顺序完美避开了重复数字相互覆盖的问题（例如 [3, 3] 找 6），也保证了绝不会在第一个数字就发生错误的匹配。

题目 2：字母异位词分组 (LeetCode 49)

原题

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。

  • 示例: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] -> 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import collections

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 使用自带兜底功能的字典，键不存在时自动创建空列表
        mp = collections.defaultdict(list)
        
        for st in strs:
            # 寻找统一特征：排序并转为不可变的元组作为键
            key = tuple(sorted(st)) 
            # 将原始单词挂载到对应键的列表中
            mp[key].append(st)      
            
        # 提取所有的分组列表并返回
        return list(mp.values())

解析

  • 核心逻辑：为所有打乱的单词寻找一个统一的接头暗号作为字典的键。如果两个单词是字母异位词，它们按字母表排序后的结果一定完全相同。
  • 底层踩坑：sorted() 函数返回的是列表（可变类型），而 Python 字典要求键必须是不可变的（拥有固定指纹）。因此必须使用 tuple() 或 "".join() 将其转换为不可变的元组或字符串，才能安全地作为键。
  • API 技巧：collections.defaultdict(list) 省去了我们手动写 if key not in mp: 的判断逻辑，代码更加优雅。

题目 3：最长连续序列 (LeetCode 128)

原题

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

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

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 将列表转换为集合 (Set)，本质上是只有键没有值的哈希表，实现 O(1) 查找并去重
        num_set = set(nums) 
        longest_streak = 0

        for num in num_set:
            # 核心剪枝逻辑：只有当 num - 1 不在集合中时，说明 num 是一个连续序列的“起点”
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                # 顺藤摸瓜，不断去哈希表中寻找下一个连续数字
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                # 更新历史最长记录
                longest_streak = max(longest_streak, current_streak)

        return longest_streak

解析

  • 突破口：题目要求时间复杂度 $O(n)$，直接封死了先用 sort() 排序（$O(n \log n)$）的路子。要想在乱序中快速寻找连续数字，必须借助哈希表的 $O(1)$ 查找能力。
  • 数据结构选择：这道题我们只需要判断数字“存不存在”，不需要记录它的索引，所以我们使用 集合 (set)。它是极简版的字典。
  • 核心算法思维（剪枝）：如果我们对集合里的每一个数都向上找一遍（比如遇到 2 找一遍，遇到 3 又找一遍），时间复杂度会退化。绝妙的思路是找“序列的起点”。
    • 怎么判断一个数是起点？只要 它减去 1 的那个数不在集合里，它就是龙头！
    • 我们只对“龙头”进行向上的循环计数。这样每个数字实际上最多只被遍历两次，完美达成 $O(n)$ 的时间复杂度要求。