← 返回

LeetCode HOT100 中等题

首发 2026/05/10 阅读 10 评论 0 更新 2026/05/10

LeetCode HOT100 中等题详细学习版

1. LC 2 两数相加
1. LC 3 无重复字符的最长子串
1. LC 5 最长回文子串
1. LC 11 盛最多水的容器
1. LC 15 三数之和
1. LC 17 电话号码的字母组合
1. LC 19 删除链表的倒数第 N 个结点
1. LC 22 括号生成
1. LC 31 下一个排列
1. LC 33 搜索旋转排序数组
1. LC 34 在排序数组中查找元素的第一个和最后一个位置
1. LC 39 组合总和
1. LC 46 全排列
1. LC 48 旋转图像
1. LC 49 字母异位词分组
1. LC 53 最大子数组和
1. LC 55 跳跃游戏
1. LC 56 合并区间
1. LC 62 不同路径
1. LC 64 最小路径和
1. LC 75 颜色分类
1. LC 78 子集
1. LC 79 单词搜索
1. LC 96 不同的二叉搜索树
1. LC 98 验证二叉搜索树
1. LC 102 二叉树的层序遍历
1. LC 105 从前序与中序遍历序列构造二叉树
1. LC 114 二叉树展开为链表
1. LC 128 最长连续序列
1. LC 139 单词拆分
1. LC 142 环形链表 II
1. LC 146 LRU 缓存
1. LC 148 排序链表
1. LC 152 乘积最大子数组
1. LC 155 最小栈
1. LC 198 打家劫舍
1. LC 200 岛屿数量
1. LC 207 课程表
1. LC 208 实现 Trie 前缀树
1. LC 215 数组中的第 K 个最大元素
1. LC 221 最大正方形
1. LC 236 二叉树的最近公共祖先
1. LC 238 除自身以外数组的乘积
1. LC 240 搜索二维矩阵 II
1. LC 279 完全平方数
1. LC 287 寻找重复数
1. LC 300 最长递增子序列
1. LC 309 最佳买卖股票时机含冷冻期
1. LC 322 零钱兑换
1. LC 337 打家劫舍 III
1. LC 347 前 K 个高频元素
1. LC 394 字符串解码
1. LC 399 除法求值
1. LC 406 根据身高重建队列
1. LC 416 分割等和子集
1. LC 437 路径总和 III
1. LC 438 找到字符串中所有字母异位词
1. LC 494 目标和
1. LC 538 把二叉搜索树转换为累加树
1. LC 560 和为 K 的子数组
1. LC 581 最短无序连续子数组
1. LC 621 任务调度器
1. LC 647 回文子串
1. LC 739 每日温度

1. LC 2 两数相加

难度：中等
标签：链表、数学

原题简述

两个逆序链表表示整数，返回相加后的逆序链表。

知识点介绍

竖式加法：每一位相加后只保留个位，十位作为进位 carry。

标准思路

同时遍历两个链表，空节点按 0 处理；循环条件要包含最后可能剩下的 carry。

最优标准解

python

from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()                    # 虚拟头节点，方便把每一位结果依次接上
        cur = dummy                           # cur 指向结果链表尾部，后面新节点都接在它后面
        carry = 0                             # carry 保存上一位加法产生的进位
        while l1 or l2 or carry:              # 链表没走完或还有进位时，都要继续计算下一位
            x = l1.val if l1 else 0           # 取 l1 当前位；l1 走完时按 0 处理
            y = l2.val if l2 else 0           # 取 l2 当前位；l2 走完时按 0 处理
            total = x + y + carry             # 当前位总和 = 两个节点值 + 进位
            carry = total // 10               # 十位部分作为下一轮进位
            cur.next = ListNode(total % 10)   # 当前节点只能存个位数
            cur = cur.next                    # 结果链表尾指针后移
            if l1:                            # 当前链表还有节点时，指针才能后移
                l1 = l1.next                  # l1 移到下一位
            if l2:                            # 当前链表还有节点时，指针才能后移
                l2 = l2.next                  # l2 移到下一位
        return dummy.next                     # 返回虚拟头节点后面的真实链表头

复杂度

时间 O(max(m,n))，空间 O(max(m,n))。

易错点

循环条件必须包含 carry；空链表节点按 0 处理。

多解补充

多解 1：递归

取舍说明： 同样正确，但递归栈更占空间。

python

from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def dfs(a, b, carry):
            if not a and not b and carry == 0:
                return None                   # 没有可返回的节点或结果
            x = a.val if a else 0             # 取 l1 当前位；l1 走完时按 0 处理
            y = b.val if b else 0             # 取 l2 当前位；l2 走完时按 0 处理
            total = x + y + carry             # 当前位总和 = 两个节点值 + 进位
            node = ListNode(total % 10)       # 当前节点只能存个位数
            node.next = dfs(a.next if a else None, b.next if b else None, total // 10)  # 递归处理下一位，并把结果接到当前节点后面
            return node                       # 返回当前构造出的节点
        return dfs(l1, l2, 0)

快速复习

链表加法：个位建节点，十位进位。

2. LC 3 无重复字符的最长子串

难度：中等
标签：字符串、滑动窗口、哈希表

原题简述

返回不含重复字符的最长连续子串长度。

知识点介绍

窗口表示当前没有重复字符的一段，字典记录字符最近出现位置。

标准思路

右指针遍历；如果字符上次出现位置在窗口内，left 跳到上次位置后一位。

最优标准解

python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}                             # 记录每个字符最近一次出现的位置
        left = 0                              # 窗口左边界，保证窗口内没有重复字符
        ans = 0                               # 记录目前最长无重复子串长度
        for right, ch in enumerate(s):        # right 是窗口右边界，ch 是当前加入窗口的字符
            if ch in last and last[ch] >= left:  # 当前字符上次出现位置仍在窗口内，说明重复了
                left = last[ch] + 1           # 左边界跳到重复字符上次出现位置后一位
            last[ch] = right                  # 更新当前字符的最新位置
            ans = max(ans, right - left + 1)  # 用当前合法窗口长度更新答案
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(k)。

易错点

判断重复要看上次位置是否 >= left。

多解补充

多解 1：set 窗口

取舍说明： 更直观，但遇到重复时需要一步步删除。

python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = set()
        left = ans = 0                        # 记录目前找到的最长无重复子串长度
        for right, ch in enumerate(s):        # right 是窗口右边界，ch 是当前加入窗口的字符
            while ch in window:
                window.remove(s[left])
                left += 1
            window.add(ch)
            ans = max(ans, right - left + 1)  # 用当前合法窗口长度更新答案
        return ans                            # 返回最终答案

快速复习

无重复子串：滑动窗口 + 最近下标。

3. LC 5 最长回文子串

难度：中等
标签：字符串、中心扩展、动态规划

原题简述

返回字符串中的最长回文连续子串。

知识点介绍

回文串有中心，可能是一个字符，也可能是两个字符之间。

标准思路

枚举每个中心，向左右扩展，记录最长合法范围。

最优标准解

python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start = end = 0                       # 记录当前最长回文子串左边界
        def expand(l, r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return l + 1, r - 1
        for i in range(len(s)):
            l1, r1 = expand(i, i)             # 以单个字符为中心，找奇数长度回文
            l2, r2 = expand(i, i + 1)         # 以两个字符中间为中心，找偶数长度回文
            if r1 - l1 > end - start:
                start, end = l1, r1           # 记录当前最长回文子串左边界
            if r2 - l2 > end - start:
                start, end = l2, r2           # 记录当前最长回文子串左边界
        return s[start:end + 1]               # 根据最终边界切出最长回文子串

复杂度

时间 O(n²)，空间 O(1)。

易错点

偶数中心不能漏；切片右边界要 end+1。

多解补充

多解 1：动态规划

取舍说明： 能体现标签，但空间 O(n²)，不如中心扩展省。

python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]  # dp[i][j] 表示 s[i:j+1] 是否为回文
        start = max_len = 0                   # 记录当前最长回文子串长度
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and (length <= 2 or dp[i + 1][j - 1]):  # 两端字符相同，才有可能形成回文
                    dp[i][j] = True
                    if length > max_len:
                        start, max_len = i, length  # 记录当前最长回文子串长度
        return s[start:start + max_len]       # 根据最终边界切出最长回文子串

快速复习

最长回文子串：枚举中心向外扩。

4. LC 11 盛最多水的容器

难度：中等
标签：数组、双指针

原题简述

给定柱子高度，选两根柱子和 x 轴组成容器，求最大盛水面积。

知识点介绍

面积由宽度和短板决定；宽度缩小时，只有移动短板才可能提高高度。

标准思路

左右指针从两端开始，每次计算面积，移动较短的一边。

最优标准解

python

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        ans = 0                               # 记录目前能装的最大水量
        while left < right:
            area = (right - left) * min(height[left], height[right])  # 当前面积 = 左右距离 × 较短柱子高度
            ans = max(ans, area)              # 用当前容器面积更新最大值
            if height[left] < height[right]:  # 左边是短板，移动它才可能找到更高水位
                left += 1                     # 移动左短板，尝试提高容器高度
            else:
                right -= 1                    # 移动右短板，尝试提高容器高度
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(1)。

易错点

移动长板不能突破短板限制；循环条件是 left<right。

多解补充

多解 1：暴力枚举

取舍说明： 能做但 O(n²)，会超时。

python

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ans = 0                               # 记录目前能装的最大水量
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                ans = max(ans, (j - i) * min(height[i], height[j]))  # 用当前容器面积更新最大值
        return ans                            # 返回最终答案

快速复习

容器问题：移动短板。

5. LC 15 三数之和

难度：中等
标签：数组、排序、双指针

原题简述

找出所有不重复三元组，使三数之和为 0。

知识点介绍

排序后固定一个数，问题转成两数之和；相同元素相邻方便去重。

标准思路

遍历 i 固定第一个数，在右侧用 left/right 找两数；找到答案后跳过重复。

最优标准解

python

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()                           # 先排序，方便双指针移动和去重
        ans = []                              # 保存所有符合条件的不重复三元组
        n = len(nums)                         # 数组长度，后面循环和边界判断会用到
        for i in range(n - 2):                # 固定第一个数，后面至少还要留两个数
            if nums[i] > 0:                   # 固定数已大于 0，后面也不小于它，不可能凑成 0
                break
            if i > 0 and nums[i] == nums[i - 1]:  # 跳过重复固定数，避免重复三元组
                continue
            left, right = i + 1, n - 1        # 左右指针分别从固定数右侧和数组末尾开始
            while left < right:               # 左右指针没有相遇时，继续寻找另外两个数
                total = nums[i] + nums[left] + nums[right]  # 计算当前三元组和，用它决定指针移动方向
                if total == 0:
                    ans.append([nums[i], nums[left], nums[right]])  # 当前三数之和为 0，记录这一组三元组
                    left += 1                 # 左指针右移，继续寻找下一组可能答案
                    right -= 1                # 右指针左移，继续寻找下一组可能答案
                    while left < right and nums[left] == nums[left - 1]:  # 跳过左侧重复值，避免重复答案
                        left += 1             # 左指针右移，继续寻找下一组可能答案
                    while left < right and nums[right] == nums[right + 1]:  # 跳过右侧重复值，避免重复答案
                        right -= 1            # 右指针左移，继续寻找下一组可能答案
                elif total < 0:               # 总和太小，需要更大的数
                    left += 1                 # 左指针右移，继续寻找下一组可能答案
                else:                         # 总和太大，需要更小的数
                    right -= 1                # 右指针左移，继续寻找下一组可能答案
        return ans                            # 返回最终答案

复杂度

时间 O(n²)，空间 O(1) 不算答案。

易错点

固定数、left、right 都要去重；排序是关键。

多解补充

多解 1：哈希两数之和思路

取舍说明： 可做但去重更麻烦，不如排序双指针清晰。

python

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = set()
        n = len(nums)                         # 数组长度，后面循环和边界判断会用到
        for i in range(n):
            seen = set()                      # 记录固定 nums[i] 后，已经见过的第二个数
            for j in range(i + 1, n):
                need = -nums[i] - nums[j]     # 计算第三个数需要是多少，才能让三数之和为 0
                if need in seen:              # 需要的第三个数已经出现过，得到一组三元组
                    ans.add(tuple(sorted((nums[i], nums[j], need))))  # 排序后放入集合，借助集合去重
                seen.add(nums[j])             # 把当前第二个数记录下来，供后面匹配
        return [list(t) for t in ans]

快速复习

三数之和：排序 + 固定一数 + 双指针。

6. LC 17 电话号码的字母组合

难度：中等
标签：回溯、字符串

原题简述

给定数字 2-9，返回它们能表示的所有字母组合。

知识点介绍

每个数字对应多个字母，组合问题适合回溯。

标准思路

按 digit 位置递归选择一个字母，路径长度等于 digits 长度时加入答案。

最优标准解

python

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:                        # 没有输入数字时，没有任何字母组合
            return []
        mp = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}  # 数字到字母的映射表
        ans, path = [], []                    # ans 保存所有组合，path 保存当前正在构造的组合
        def backtrack(i):
            if i == len(digits):              # 每个数字都选完一个字母，得到完整组合
                ans.append(''.join(path))     # 把路径中的字母拼成字符串加入答案
                return                        # 结束当前递归分支
            for ch in mp[digits[i]]:          # 枚举当前数字能对应的所有字母
                path.append(ch)               # 加入当前路径、节点或中间结果
                backtrack(i + 1)              # 递归处理下一个数字
                path.pop()                    # 撤销当前选择，尝试下一个字母
        backtrack(0)
        return ans                            # 返回最终答案

复杂度

时间 O(4^n)，空间 O(n) 不算答案。

易错点

空字符串返回 []；回溯后要 pop。

多解补充

多解 1：队列迭代

取舍说明： 同样正确，按层扩展组合。

python

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:                        # 没有输入数字时，没有任何字母组合
            return []
        mp = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}  # 数字到字母的映射表
        ans = ['']
        for d in digits:
            ans = [prefix + ch for prefix in ans for ch in mp[d]]
        return ans                            # 返回最终答案

快速复习

组合问题：路径 + 选择 + 撤销。

7. LC 19 删除链表的倒数第 N 个结点

难度：中等
标签：链表、双指针

原题简述

删除链表倒数第 n 个节点，返回头节点。

知识点介绍

快慢指针保持 n+1 距离，让 slow 停在待删节点前一个。

标准思路

dummy 防止删除头节点特殊处理；fast 先走 n+1 步，再同步走。

最优标准解

python

from typing import Optional

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)             # 虚拟头节点，方便统一处理链表头部变化
        fast = slow = dummy                   # 虚拟头节点，方便统一处理链表头部变化
        for _ in range(n + 1):                # fast 先走 n+1 步，让 slow 停在待删节点前一个
            fast = fast.next
        while fast:                           # 快慢指针保持距离，同时向后走
            fast = fast.next
            slow = slow.next                  # slow 每次走一步
        slow.next = slow.next.next            # 跳过 slow 后面的节点，完成删除
        return dummy.next                     # 返回虚拟头节点后面的真实链表头

复杂度

时间 O(n)，空间 O(1)。

易错点

用 dummy 处理删除头节点；fast 先走 n+1。

多解补充

多解 1：两遍扫描

取舍说明： 更直观但不是一趟。

python

from typing import Optional

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)             # 虚拟头节点，方便统一处理链表头部变化
        length, cur = 0, head
        while cur:
            length += 1
            cur = cur.next
        cur = dummy                           # 虚拟头节点，方便统一处理链表头部变化
        for _ in range(length - n):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next                     # 返回虚拟头节点后面的真实链表头

快速复习

倒数第 n 个：快慢指针拉开距离。

8. LC 22 括号生成

难度：中等
标签：回溯

原题简述

生成 n 对括号的所有合法组合。

知识点介绍

合法括号构造过程：左括号数量不能超过 n，右括号数量不能超过左括号。

标准思路

回溯时记录 left/right 已用数量，合法时继续添加。

最优标准解

python

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans, path = [], []                    # ans 保存所有合法结果，path 保存当前括号串
        def backtrack(left, right):
            if len(path) == 2 * n:            # 长度达到 2n，说明形成一个完整括号串
                ans.append(''.join(path))
                return                        # 结束当前递归分支
            if left < n:                      # 左括号还没用完，可以继续放左括号
                path.append('(')              # 加入当前路径、节点或中间结果
                backtrack(left + 1, right)
                path.pop()                    # 撤销刚才放入的括号，尝试其他选择
            if right < left:                  # 右括号少于左括号时，才能放右括号保持合法
                path.append(')')              # 加入当前路径、节点或中间结果
                backtrack(left, right + 1)
                path.pop()                    # 撤销刚才放入的括号，尝试其他选择
        backtrack(0, 0)
        return ans                            # 返回最终答案

复杂度

时间约 O(Catalan(n))，空间 O(n)。

易错点

右括号数量不能超过左括号。

多解补充

多解 1：暴力生成后过滤

取舍说明： 能做但大量无效字符串，不推荐。

python

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def valid(s):
            bal = 0
            for ch in s:
                bal += 1 if ch == '(' else -1
                if bal < 0:
                    return False              # 当前情况不符合题意
            return bal == 0
        def dfs(s):
            if len(s) == 2*n:
                if valid(s):
                    ans.append(s)
                return                        # 结束当前递归分支
            dfs(s + '(')
            dfs(s + ')')
        dfs('')
        return ans                            # 返回最终答案

快速复习

生成括号：左可加、右不超过左。

9. LC 31 下一个排列

难度：中等
标签：数组、双指针

原题简述

把数组改成字典序下一个更大的排列；若不存在则变最小排列。

知识点介绍

从右往左找第一个下降点，再找右侧刚好比它大的数交换，最后反转后缀。

标准思路

后缀从右看是非递增的，交换后反转成最小后缀。

最优标准解

python

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i = len(nums) - 2                     # 从右往左找第一个下降位置
        while i >= 0 and nums[i] >= nums[i + 1]:  # 当前位置还不是需要变大的位置，继续向左找
            i -= 1
        if i >= 0:
            j = len(nums) - 1                 # 从右侧找第一个比 nums[i] 大的数
            while nums[j] <= nums[i]:         # 这个数不够大，继续向左找
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]  # 交换后，排列刚好变大一点
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

复杂度

时间 O(n)，空间 O(1)。

易错点

找下降点；交换后必须反转后缀。

多解补充

多解 1：用排序后缀

取舍说明： 逻辑相同但后缀排序 O(n log n)，不如反转。

python

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        i = len(nums) - 2                     # 从右往左找第一个下降位置
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1                 # 从右侧找第一个比 nums[i] 大的数
            while nums[j] <= nums[i]:         # 这个数不够大，继续向左找
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]  # 交换后，排列刚好变大一点
        nums[i+1:] = sorted(nums[i+1:])

快速复习

下一个排列：找下降点、换更大、反转后缀。

10. LC 33 搜索旋转排序数组

难度：中等
标签：数组、二分

原题简述

在旋转后的升序数组中搜索 target。

知识点介绍

旋转数组任意二分后，至少有一半是有序的。

标准思路

每次判断左半还是右半有序，再决定 target 在哪边。

最优标准解

python

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1        # 二分查找的左右边界
        while left <= right:
            mid = (left + right) // 2         # 取中点，判断目标落在哪一侧
            if nums[mid] == target:           # 中点就是目标值
                return mid
            if nums[left] <= nums[mid]:       # 左半段有序，可以判断 target 是否在左半段
                if nums[left] <= target < nums[mid]:
                    right = mid - 1           # 排除右侧不可能区间
                else:
                    left = mid + 1            # 排除左侧不可能区间
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1            # 排除左侧不可能区间
                else:
                    right = mid - 1           # 排除右侧不可能区间
        return -1

复杂度

时间 O(log n)，空间 O(1)。

易错点

判断哪半有序；边界用闭区间。

多解补充

多解 1：线性查找

取舍说明： 简单但 O(n)，不是题目要求。

python

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i, x in enumerate(nums):
            if x == target:
                return i
        return -1

快速复习

旋转数组搜索：二分找有序半边。

11. LC 34 在排序数组中查找元素的第一个和最后一个位置

难度：中等
标签：数组、二分

原题简述

在升序数组中返回 target 的起止下标，不存在返回 [-1,-1]。

知识点介绍

找左右边界本质是两次二分。

标准思路

一次找第一个 >= target 的位置，一次找第一个 > target 的位置减一。

最优标准解

python

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def lower_bound(x):
            left, right = 0, len(nums)        # 二分查找的左右边界
            while left < right:
                mid = (left + right) // 2     # 取中点，判断目标落在哪一侧
                if nums[mid] < x:
                    left = mid + 1            # 排除左侧不可能区间
                else:
                    right = mid               # 排除右侧不可能区间
            return left
        l = lower_bound(target)
        r = lower_bound(target + 1) - 1
        if l <= r and l < len(nums) and nums[l] == target:
            return [l, r]
        return [-1, -1]

复杂度

时间 O(log n)，空间 O(1)。

易错点

注意空数组和不存在情况。

多解补充

多解 1：线性扫描

取舍说明： 能做但 O(n)。

python

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = [-1, -1]
        for i, x in enumerate(nums):
            if x == target:
                if ans[0] == -1:
                    ans[0] = i
                ans[1] = i
        return ans                            # 返回最终答案

快速复习

边界查找：lower_bound 两次。

12. LC 39 组合总和

难度：中等
标签：回溯

原题简述

给定候选数和目标，返回所有和为 target 的组合，每个数可重复使用。

知识点介绍

组合问题用回溯；为了不重复组合，递归传入 start 限制选择顺序。

标准思路

每次从 start 开始选数，选中后 target 减小；因为可重复使用，下一层仍从当前 i 开始。

最优标准解

python

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans, path = [], []
        candidates.sort()                     # 排序后方便利用有序性
        def dfs(start, remain):
            if remain == 0:                   # 剩余目标为 0，当前路径就是一个合法组合
                ans.append(path[:])           # 把当前路径拷贝进答案，避免后续回溯修改
                return                        # 结束当前递归分支
            for i in range(start, len(candidates)):  # 从 start 开始选择，避免组合顺序不同造成重复
                x = candidates[i]
                if x > remain:
                    break
                path.append(x)                # 加入当前路径、节点或中间结果
                dfs(i, remain - x)
                path.pop()                    # 撤销选择，继续尝试下一个候选
        dfs(0, target)
        return ans                            # 返回最终答案

复杂度

时间与答案数量相关，最坏指数级；空间 O(target/min)。

易错点

可重复使用时下一层传 i，不是 i+1。

多解补充

多解 1：不排序版本

取舍说明： 也能做，但无法剪枝，效率差些。

python

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans, path = [], []
        def dfs(start, remain):
            if remain == 0:                   # 剩余目标为 0，当前路径就是一个合法组合
                ans.append(path[:])           # 把当前路径拷贝进答案，避免后续回溯修改
            return                            # 结束当前递归分支
            if remain < 0:
                return                        # 结束当前递归分支
            for i in range(start, len(candidates)):  # 从 start 开始选择，避免组合顺序不同造成重复
                path.append(candidates[i])    # 加入当前路径、节点或中间结果
                dfs(i, remain - candidates[i])
                path.pop()                    # 撤销选择，继续尝试下一个候选
        dfs(0, target)
        return ans                            # 返回最终答案

快速复习

组合总和：回溯 + start 去重。

13. LC 46 全排列

难度：中等
标签：回溯

原题简述

返回数组所有可能排列。

知识点介绍

排列问题每个位置都要尝试一个未使用元素。

标准思路

用 used 标记已选元素，路径长度等于 n 时收集答案。

最优标准解

python

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans, path = [], []
        used = [False] * len(nums)            # 记录当前排列中哪些数字已经被使用
        def dfs():
            if len(path) == len(nums):
                ans.append(path[:])           # 把当前路径拷贝进答案，避免后续回溯修改
                return                        # 结束当前递归分支
            for i, x in enumerate(nums):
                if used[i]:
                    continue
                used[i] = True                # 记录当前排列中哪些数字已经被使用
                path.append(x)                # 加入当前路径、节点或中间结果
                dfs()
                path.pop()                    # 撤销选择，继续尝试下一个候选
                used[i] = False               # 记录当前排列中哪些数字已经被使用
        dfs()
        return ans                            # 返回最终答案

复杂度

时间 O(n·n!)，空间 O(n)。

易错点

每层回溯后必须撤销 used 和 path。

多解补充

多解 1：交换法

取舍说明： 同样优秀，原地交换确定每个位置。

python

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def dfs(pos):
            if pos == len(nums):
                ans.append(nums[:])
                return                        # 结束当前递归分支
            for i in range(pos, len(nums)):
                nums[pos], nums[i] = nums[i], nums[pos]
                dfs(pos + 1)
                nums[pos], nums[i] = nums[i], nums[pos]
        dfs(0)
        return ans                            # 返回最终答案

快速复习

全排列：路径 + used。

14. LC 48 旋转图像

难度：中等
标签：矩阵、原地操作

原题简述

将 n×n 矩阵顺时针旋转 90 度，要求原地。

知识点介绍

顺时针旋转 = 先上下翻转，再沿主对角线翻转。

标准思路

先交换第 i 行和第 n-1-i 行，再交换 matrix[i][j] 与 matrix[j][i]。

最优标准解

python

from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            matrix[i], matrix[n - 1 - i] = matrix[n - 1 - i], matrix[i]
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]  # 沿主对角线交换，先完成矩阵转置

复杂度

时间 O(n²)，空间 O(1)。

易错点

对角线交换 j 从 i+1 开始；不要新建矩阵。

多解补充

多解 1：四点轮换

取舍说明： 同样原地，但下标更容易写错。

python

from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range(i, n - 1 - i):
                tmp = matrix[i][j]
                matrix[i][j] = matrix[n-1-j][i]
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j]
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i]
                matrix[j][n-1-i] = tmp

快速复习

旋转图像：上下翻转 + 转置。

15. LC 49 字母异位词分组

难度：中等
标签：哈希表、字符串

原题简述

把由相同字母组成的字符串分到同一组。

知识点介绍

异位词排序后相同；也可用 26 个字母计数作为 key。

标准思路

遍历每个字符串，用排序后的字符串作为哈希 key 分组。

最优标准解

python

from typing import List
from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)            # 按同一种特征把异位词放进同一组
        for s in strs:
            key = ''.join(sorted(s))          # 异位词排序后字符串相同，可作为分组 key
            groups[key].append(s)             # 加入当前路径、节点或中间结果
        return list(groups.values())

复杂度

设字符串总长度 L，排序法时间约 O(L log L)，空间 O(L)。

易错点

key 必须可哈希；列表不能直接做 key。

多解补充

多解 1：字母计数 key

取舍说明： 更接近 O(L)，适合只含小写字母。

python

from typing import List
from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)            # 按同一种特征把异位词放进同一组
        for s in strs:
            cnt = [0] * 26
            for ch in s:
                cnt[ord(ch) - ord('a')] += 1
            groups[tuple(cnt)].append(s)      # 加入当前路径、节点或中间结果
        return list(groups.values())

快速复习

异位词分组：排序字符串做 key。

16. LC 53 最大子数组和

难度：中等
标签：数组、动态规划

原题简述

返回连续子数组的最大和。

知识点介绍

如果前面的和为负，继续接上只会拖累当前数。

标准思路

cur 表示以当前位置结尾的最大子数组和，ans 表示全局最大。

最优标准解

python

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = ans = nums[0]                   # cur 表示以当前位置结尾的最大子数组和
        for x in nums[1:]:
            cur = max(x, cur + x)             # 要么接上前面的子数组，要么从当前数重新开始
            ans = max(ans, cur)               # 用当前位置结尾的最大和更新全局答案
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(1)。

易错点

全负数时不能把答案初始化为 0。

多解补充

多解 1：分治

取舍说明： 同样可做，但代码更长；适合理解线段树思想。

python

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def solve(l, r):
            if l == r:
                return nums[l]
            m = (l + r) // 2
            left_best = solve(l, m)
            right_best = solve(m + 1, r)
            s = 0
            best_l = float('-inf')
            for i in range(m, l - 1, -1): s += nums[i]
            best_l = max(best_l, s)
            s = 0
            best_r = float('-inf')
            for i in range(m + 1, r + 1): s += nums[i]
            best_r = max(best_r, s)
            return max(left_best, right_best, best_l + best_r)
        return solve(0, len(nums) - 1)

快速复习

最大子数组：当前要么重开，要么延续。

17. LC 55 跳跃游戏

难度：中等
标签：贪心

原题简述

判断能否从下标 0 跳到最后一个下标。

知识点介绍

维护目前能到达的最远位置。若当前下标超过最远位置，说明到不了。

标准思路

遍历每个位置，更新 far=max(far,i+nums[i])。

最优标准解

python

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        far = 0                               # far 记录当前最远能到达的位置
        for i, step in enumerate(nums):
            if i > far:                       # 当前位置都到不了，说明无法到达终点
                return False                  # 当前情况不符合题意
            far = max(far, i + step)          # far 记录当前最远能到达的位置
            if far >= len(nums) - 1:          # far 记录当前最远能到达的位置
                return True                   # 当前检查通过
        return True                           # 当前检查通过

复杂度

时间 O(n)，空间 O(1)。

易错点

不是每一步跳最远，而是维护覆盖范围。

多解补充

多解 1：DP 可达性

取舍说明： 能做但 O(n²)，不如贪心。

python

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[0] = True
        for i in range(n):
            if not dp[i]:
                continue
            for j in range(i + 1, min(n, i + nums[i] + 1)):  # 从当前位置起跳，尝试更新最远可达位置
                dp[j] = True
        return dp[-1]

快速复习

跳跃游戏：维护最远可达。

18. LC 56 合并区间

难度：中等
标签：排序、数组

原题简述

合并所有重叠区间。

知识点介绍

按左端点排序后，重叠区间会相邻。

标准思路

维护结果最后一个区间；若当前左端点 <= 最后右端点，就合并右端点。

最优标准解

python

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])    # 排序后方便利用有序性
        ans = []
        for l, r in intervals:
            if not ans or l > ans[-1][1]:
                ans.append([l, r])
            else:
                ans[-1][1] = max(ans[-1][1], r)  # 当前区间和上一个区间重叠，合并右端点
        return ans                            # 返回最终答案

复杂度

时间 O(n log n)，空间 O(n) 不算排序内部。

易错点

先排序；判断重叠用当前左端点和最后右端点。

多解补充

多解 1：暴力合并

取舍说明： 能做但复杂且低效，不推荐。

python

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()                      # 排序后方便利用有序性
        changed = True
        while changed:
            changed = False
            res = []
            for itv in intervals:
                if res and itv[0] <= res[-1][1]:
                    res[-1][1] = max(res[-1][1], itv[1])
                    changed = True
                else:
                    res.append(itv)           # 加入当前路径、节点或中间结果
            intervals = res
        return intervals

快速复习

合并区间：按左端点排序。

19. LC 62 不同路径

难度：中等
标签：动态规划

原题简述

机器人只能向右或向下，从左上到右下共有多少路径。

知识点介绍

到某格只能从上方或左方来。

标准思路

dp[j] 表示当前行第 j 列路径数，dp[j]+=dp[j-1]。

最优标准解

python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n                          # 创建 DP 表，保存子问题答案
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]            # 创建 DP 表，保存子问题答案
        return dp[-1]

复杂度

时间 O(mn)，空间 O(n)。

易错点

第一行第一列都是 1。

多解补充

多解 1：组合数学

取舍说明： 同样优秀，代码短但需要理解组合数。

python

import math

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return math.comb(m + n - 2, m - 1)

快速复习

路径 DP：上 + 左。

20. LC 64 最小路径和

难度：中等
标签：动态规划、矩阵

原题简述

从左上到右下，只能向右或向下，求路径数字和最小值。

知识点介绍

到某格最小代价来自上方或左方的较小者。

标准思路

原地修改 grid，让 grid[i][j] 表示到该格的最小路径和。

最优标准解

python

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                up = grid[i - 1][j] if i > 0 else float('inf')
                left = grid[i][j - 1] if j > 0 else float('inf')
                grid[i][j] += min(up, left)   # 在不同选择中取代价最小的方案
        return grid[-1][-1]

复杂度

时间 O(mn)，空间 O(1)。

易错点

首行首列边界处理；可以原地改。

多解补充

多解 1：额外 DP 表

取舍说明： 不修改原 grid，但空间 O(mn)。

python

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0]*n for _ in range(m)]        # 创建 DP 表，保存子问题答案
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]     # 创建 DP 表，保存子问题答案
                else:
                    up = dp[i-1][j] if i else float('inf')  # 创建 DP 表，保存子问题答案
                    left = dp[i][j-1] if j else float('inf')  # 创建 DP 表，保存子问题答案
                    dp[i][j] = grid[i][j] + min(up, left)  # 创建 DP 表，保存子问题答案
        return dp[-1][-1]

快速复习

最小路径和：当前值 + min(上,左)。

21. LC 75 颜色分类

难度：中等
标签：数组、双指针

原题简述

原地排序只包含 0、1、2 的数组。

知识点介绍

荷兰国旗问题：左边放 0，中间放 1，右边放 2。

标准思路

p0 指向下一个 0 位置，p2 指向下一个 2 位置，i 扫描。

最优标准解

python

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0, i, p2 = 0, 0, len(nums) - 1
        while i <= p2:
            if nums[i] == 0:                  # 当前是 0，交换到左侧 0 区
                nums[p0], nums[i] = nums[i], nums[p0]
                p0 += 1
                i += 1                        # 当前位置已经处理好，继续扫描下一位
            elif nums[i] == 2:                # 当前是 2，交换到右侧 2 区
                nums[p2], nums[i] = nums[i], nums[p2]
                p2 -= 1
            else:
                i += 1                        # 当前位置已经处理好，继续扫描下一位

复杂度

时间 O(n)，空间 O(1)。

易错点

遇到 2 交换后 i 不加，因为换来的数未知。

多解补充

多解 1：计数排序

取舍说明： 简单但需要两遍。

python

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        cnt = [0, 0, 0]
        for x in nums: cnt[x] += 1
        idx = 0
        for color in range(3):
            for _ in range(cnt[color]):
                nums[idx] = color
                idx += 1

快速复习

颜色分类：三指针荷兰国旗。

22. LC 78 子集

难度：中等
标签：回溯、位运算

原题简述

返回数组所有子集。

知识点介绍

每个元素都有选或不选两种选择。

标准思路

回溯从 start 往后选择，每个路径都是一个子集。

最优标准解

python

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans, path = [], []
        def dfs(start):
            ans.append(path[:])               # 把当前路径拷贝进答案，避免后续回溯修改
            for i in range(start, len(nums)):  # 从 start 开始选择，避免组合顺序不同造成重复
                path.append(nums[i])          # 加入当前路径、节点或中间结果
                dfs(i + 1)
                path.pop()                    # 撤销选择，继续尝试下一个候选
        dfs(0)
        return ans                            # 返回最终答案

复杂度

时间 O(n·2^n)，空间 O(n) 不算答案。

易错点

每个路径都要加入答案，不只叶子节点。

多解补充

多解 1：位掩码

取舍说明： 同样经典，用二进制位表示选不选。

python

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        for mask in range(1 << n):
            cur = []
            for i in range(n):
                if mask & (1 << i):
                    cur.append(nums[i])       # 加入当前路径、节点或中间结果
            ans.append(cur)
        return ans                            # 返回最终答案

快速复习

子集：每层都收集路径。

23. LC 79 单词搜索

难度：中等
标签：回溯、矩阵 DFS

原题简述

在字符网格中判断是否存在一条相邻路径拼出 word。

知识点介绍

路径不能重复使用同一个格子，适合 DFS 回溯。

标准思路

从每个格子尝试作为起点，匹配一个字符后向四周扩展，走完后恢复标记。

最优标准解

python

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        def dfs(i, j, k):
            if k == len(word):
                return True                   # 当前检查通过
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:  # 当前格子字符不匹配，当前路径失败
                return False                  # 当前情况不符合题意
            ch = board[i][j]
            board[i][j] = '#'                 # 临时标记当前格子已使用，防止本路径重复走
            ok = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
            board[i][j] = ch
            return ok
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True               # 当前检查通过
        return False                          # 当前情况不符合题意

复杂度

时间 O(mn·4^L)，空间 O(L)。

易错点

访问标记要恢复；越界和字符不等要先排除。

多解补充

多解 1：额外 visited

取舍说明： 不修改 board，但需要 O(mn) 空间。

python

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m,n=len(board),len(board[0])
        vis=set()
        def dfs(i,j,k):
            if k==len(word):
                return True                   # 当前检查通过
            if i<0 or i>=m or j<0 or j>=n or (i,j) in vis or board[i][j]!=word[k]:
                return False                  # 当前情况不符合题意
            vis.add((i,j))
            ok=dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
            vis.remove((i,j))
            return ok
        return any(dfs(i,j,0) for i in range(m) for j in range(n))

快速复习

单词搜索：矩阵回溯。

24. LC 96 不同的二叉搜索树

难度：中等
标签：动态规划、树

原题简述

给定 n，求由 1..n 能组成多少种不同 BST。

知识点介绍

选 k 为根时，左边有 k-1 个数，右边有 n-k 个数，左右组合数相乘。

标准思路

dp[i] 表示 i 个节点能组成的 BST 数量。

最优标准解

python

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1                     # 空树和单节点树是递推基础
        for nodes in range(2, n + 1):
            for left in range(nodes):
                right = nodes - 1 - left
                dp[nodes] += dp[left] * dp[right]
        return dp[n]

复杂度

时间 O(n²)，空间 O(n)。

易错点

空树数量 dp[0]=1；左右数量相乘。

多解补充

多解 1：递归记忆化

取舍说明： 同样思路，写法更接近定义。

python

from functools import lru_cache

class Solution:
    def numTrees(self, n: int) -> int:
        @lru_cache(None)
        def f(nodes):
            if nodes <= 1:
                return 1
            return sum(f(left) * f(nodes - 1 - left) for left in range(nodes))
        return f(n)

快速复习

BST 计数：枚举根，左右组合相乘。

25. LC 98 验证二叉搜索树

难度：中等
标签：树、DFS、中序遍历

原题简述

判断二叉树是否满足 BST 性质。

知识点介绍

BST 的中序遍历严格递增；也可以递归维护上下界。

标准思路

每个节点必须处于合法区间 (low, high) 内。

最优标准解

python

from typing import Optional

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node, low, high):
            if not node:
                return True                   # 当前检查通过
            if not (low < node.val < high):   # 用上下界限制当前节点值的合法范围
                return False                  # 当前情况不符合题意
            return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)  # 用上下界限制当前节点值的合法范围
        return dfs(root, float('-inf'), float('inf'))

复杂度

时间 O(n)，空间 O(h)。

易错点

不能只比较直接左右孩子；要带上下界。

多解补充

多解 1：中序遍历

取舍说明： 同样优秀，利用中序严格递增。

python

from typing import Optional

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = None
        def inorder(node):
            nonlocal prev
            if not node:
                return True                   # 当前检查通过
            if not inorder(node.left):
                return False                  # 当前情况不符合题意
            if prev is not None and node.val <= prev:
                return False                  # 当前情况不符合题意
            prev = node.val
            return inorder(node.right)
        return inorder(root)

快速复习

验证 BST：递归上下界。

26. LC 102 二叉树的层序遍历

难度：中等
标签：树、BFS

原题简述

按层返回二叉树节点值。

知识点介绍

层序遍历用队列，关键是每轮固定当前层节点数。

标准思路

队列中先放根节点；每次处理一整层并收集该层值。

最优标准解

python

from typing import List, Optional
from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        q = deque([root])                     # 队列用于按层遍历二叉树
        ans = []
        while q:
            level = []                        # 保存当前这一层的节点值
            for _ in range(len(q)):           # 固定当前层节点数量，避免和下一层混在一起
                node = q.popleft()
                level.append(node.val)        # 把当前节点值加入这一层结果
                if node.left:
                    q.append(node.left)       # 加入当前路径、节点或中间结果
                if node.right:
                    q.append(node.right)      # 加入当前路径、节点或中间结果
            ans.append(level)                 # 当前层遍历完成，加入总结果
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(n)。

易错点

每层循环前要固定 len(q)。

多解补充

多解 1：DFS 按深度收集

取舍说明： 也能做，但 BFS 更自然。

python

from typing import List, Optional

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        def dfs(node, depth):
            if not node:                      # 空节点是递归边界
                return                        # 结束当前递归分支
            if depth == len(ans):
                ans.append([])
            ans[depth].append(node.val)       # 加入当前路径、节点或中间结果
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        dfs(root, 0)
        return ans                            # 返回最终答案

快速复习

层序遍历：队列按层处理。

27. LC 105 从前序与中序遍历序列构造二叉树

难度：中等
标签：树、递归、哈希表

原题简述

根据 preorder 和 inorder 构造二叉树。

知识点介绍

前序第一个是根；中序中根左边是左子树，右边是右子树。

标准思路

用哈希表快速定位根在中序中的位置，递归构建左右区间。

最优标准解

python

from typing import List, Optional

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        pos = {v:i for i,v in enumerate(inorder)}
        pre_i = 0
        def build(l, r):
            nonlocal pre_i
            if l > r:
                return None                   # 没有可返回的节点或结果
            val = preorder[pre_i]
            pre_i += 1
            root = TreeNode(val)
            mid = pos[val]
            root.left = build(l, mid - 1)     # 递归构造左子树
            root.right = build(mid + 1, r)    # 递归构造右子树
            return root                       # 返回处理后的根节点
        return build(0, len(inorder) - 1)

复杂度

时间 O(n)，空间 O(n)。

易错点

先构建左子树再右子树，因为前序顺序是根左右。

多解补充

多解 1：切片递归

取舍说明： 好理解但切片会产生额外 O(n²) 开销。

python

from typing import List, Optional

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None                       # 没有可返回的节点或结果
        root_val = preorder[0]                # 前序区间第一个值就是当前子树根节点
        idx = inorder.index(root_val)         # 记录中序遍历中每个值的位置，方便切分左右子树
        root = TreeNode(root_val)             # 前序区间第一个值就是当前子树根节点
        root.left = self.buildTree(preorder[1:1+idx], inorder[:idx])  # 记录中序遍历中每个值的位置，方便切分左右子树
        root.right = self.buildTree(preorder[1+idx:], inorder[idx+1:])  # 记录中序遍历中每个值的位置，方便切分左右子树
        return root                           # 返回处理后的根节点

快速复习

建树：前序定根，中序分左右。

28. LC 114 二叉树展开为链表

难度：中等
标签：树、DFS、链表

原题简述

将二叉树原地展开成前序遍历顺序的右链表。

知识点介绍

展开结果是前序：根、左、右。可以后序处理，把左右子树先展开再拼接。

标准思路

记录左子树和右子树，左子树接到右边，再把原右子树接到左子树尾部。

最优标准解

python

from typing import Optional

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        cur = root
        while cur:
            if cur.left:
                pre = cur.left
                while pre.right:
                    pre = pre.right
                pre.right = cur.right
                cur.right = cur.left
                cur.left = None
            cur = cur.right

复杂度

时间 O(n²) 最坏，空间 O(1)；若用后序可 O(n)。

易错点

原地修改；左指针必须置空。

多解补充

多解 1：反向前序递归

取舍说明： 更简洁，时间 O(n)，但递归栈 O(h)。

python

from typing import Optional

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        prev = None
        def dfs(node):
            nonlocal prev
            if not node:                      # 空节点是递归边界
                return                        # 结束当前递归分支
            dfs(node.right)                   # 递归处理右子树
            dfs(node.left)                    # 递归处理左子树
            node.right = prev
            node.left = None
            prev = node
        dfs(root)

快速复习

展开树：前序右链表。

29. LC 128 最长连续序列

难度：中等
标签：哈希表

原题简述

返回数组中最长连续整数序列长度，要求 O(n)。

知识点介绍

只有当 x-1 不存在时，x 才可能是一段连续序列的起点。

标准思路

把所有数放入 set，从每个起点向后数长度。

最优标准解

python

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)                         # 集合支持 O(1) 判断某个数字是否存在
        ans = 0
        for x in s:
            if x - 1 not in s:                # 只有连续序列的起点才开始扩展，避免重复计算
                y = x
                while y in s:
                    y += 1
                ans = max(ans, y - x)
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(n)。

易错点

必须只从起点扩展，否则会退化。

多解补充

多解 1：排序

取舍说明： 可做但 O(n log n)，不满足最优要求。

python

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums = sorted(set(nums))              # 集合支持 O(1) 判断某个数字是否存在
        ans = cur = 1
        for i in range(1, len(nums)):
            cur = cur + 1 if nums[i] == nums[i-1] + 1 else 1
            ans = max(ans, cur)
        return ans                            # 返回最终答案

快速复习

连续序列：set + 找起点。

30. LC 139 单词拆分

难度：中等
标签：动态规划、字符串

原题简述

判断字符串能否被字典中的单词拼接出来。

知识点介绍

dp[i] 表示 s[:i] 能否被拆分。

标准思路

枚举结尾 i，再枚举上一个切分点 j，若 dp[j] 且 s[j:i] 在字典中则 dp[i]=True。

最优标准解

python

from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)                 # 词典转集合，快速判断子串是否是单词
        dp = [False] * (len(s) + 1)           # 创建 DP 表，保存子问题答案
        dp[0] = True                          # 创建 DP 表，保存子问题答案
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:  # 前半段可拆分且后半段是单词，则 s[:i] 可拆分
                    dp[i] = True              # 创建 DP 表，保存子问题答案
                    break
        return dp[-1]

复杂度

时间 O(n²·切片成本)，空间 O(n)。

易错点

dp[0]=True 表示空串可拆；字典用 set。

多解补充

多解 1：DFS 记忆化

取舍说明： 同样正确，适合从递归角度理解。

python

from typing import List
from functools import lru_cache

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)                 # 词典转集合，快速判断子串是否是单词
        @lru_cache(None)
        def dfs(start):
            if start == len(s):
                return True                   # 当前检查通过
            for end in range(start+1, len(s)+1):
                if s[start:end] in words and dfs(end):
                    return True               # 当前检查通过
            return False                      # 当前情况不符合题意
        return dfs(0)

快速复习

单词拆分：dp[i] 看前一个切分点。

31. LC 142 环形链表 II

难度：中等
标签：链表、双指针

原题简述

返回链表入环节点，无环返回 None。

知识点介绍

快慢指针相遇后，从头和相遇点同时走，会在入环点相遇。

标准思路

先判环，再用两个指针找入口。

最优标准解

python

from typing import Optional

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head                    # slow 找中点或入环点，fast 用来制造速度差
        while fast and fast.next:             # fast 还能走两步时，继续推进快慢指针
            slow = slow.next                  # slow 每次走一步
            fast = fast.next.next             # fast 每次走两步
            if slow is fast:                  # 快慢指针相遇，说明存在环
                p = head
                while p is not slow:
                    p = p.next
                    slow = slow.next          # slow 每次走一步
                return p
        return None                           # 没有可返回的节点或结果

复杂度

时间 O(n)，空间 O(1)。

易错点

相遇不一定是入口；第二阶段找入口。

多解补充

多解 1：哈希集合

取舍说明： 直观但空间 O(n)。

python

from typing import Optional

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        seen = set()
        while head:
            if head in seen:
                return head
            seen.add(head)
            head = head.next
        return None                           # 没有可返回的节点或结果

快速复习

环入口：相遇后头指针和相遇点同步走。

32. LC 146 LRU 缓存

难度：中等
标签：设计、哈希表、双向链表

原题简述

实现 get/put，最近最少使用的键在容量满时淘汰。

知识点介绍

哈希表负责 O(1) 找节点，双向链表负责 O(1) 调整使用顺序。

标准思路

每次访问或更新节点都移到链表尾部，头部是真正最久未使用。

最优标准解

python

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_last(self, node):
        prev = self.tail.prev
        prev.next = node
        node.prev = prev
        node.next = self.tail
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_last(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._add_last(node)
        else:
            node = Node(key, value)
            self.map[key] = node
            self._add_last(node)
            if len(self.map) > self.cap:
                old = self.head.next
                self._remove(old)
                del self.map[old.key]

复杂度

get/put 时间 O(1)，空间 O(capacity)。

易错点

删除哈希表时要用节点 key；哨兵头尾能减少边界判断。

多解补充

多解 1：OrderedDict

取舍说明： Python 简洁实现，但面试常要求手写双向链表。

python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.od = OrderedDict()               # 有序字典同时保存键值和访问顺序

    def get(self, key: int) -> int:
        if key not in self.od:
            return -1
        self.od.move_to_end(key)              # 访问过的 key 移到末尾，表示最近使用
        return self.od[key]

    def put(self, key: int, value: int) -> None:
        if key in self.od:
            self.od.move_to_end(key)          # 访问过的 key 移到末尾，表示最近使用
        self.od[key] = value
        if len(self.od) > self.cap:
            self.od.popitem(last=False)       # 容量超限时删除最久未使用的队头元素

快速复习

LRU：哈希表 + 双向链表。

33. LC 148 排序链表

难度：中等
标签：链表、归并排序

原题简述

对链表进行升序排序。

知识点介绍

链表适合归并排序，因为可以用快慢指针拆分，用指针合并。

标准思路

快慢指针找到中点断开，递归排序两半，再合并有序链表。

最优标准解

python

from typing import Optional

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        slow, fast = head, head.next          # 快慢指针找链表中点
        while fast and fast.next:             # fast 还能走两步时，继续推进快慢指针
            slow = slow.next                  # slow 每次走一步
            fast = fast.next.next             # fast 每次走两步
        mid = slow.next                       # 右半部分从 mid 开始
        slow.next = None                      # 断开左右两段，方便分别递归排序
        left = self.sortList(head)
        right = self.sortList(mid)
        dummy = cur = ListNode()              # 虚拟头节点，方便统一处理链表头部变化
        while left and right:
            if left.val <= right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        cur.next = left if left else right
        return dummy.next                     # 返回虚拟头节点后面的真实链表头

复杂度

时间 O(n log n)，空间 O(log n) 递归栈。

易错点

拆分时要断开 slow.next。

多解补充

多解 1：转数组排序

取舍说明： 简单但不是链表算法核心，空间 O(n)。

python

from typing import Optional

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        vals = []
        while head:
            vals.append(head.val)             # 加入当前路径、节点或中间结果
            head = head.next
        vals.sort()                           # 排序后方便利用有序性
        dummy = cur = ListNode()              # 虚拟头节点，方便统一处理链表头部变化
        for x in vals:
            cur.next = ListNode(x)
            cur = cur.next
        return dummy.next                     # 返回虚拟头节点后面的真实链表头

快速复习

链表排序：归并最自然。

34. LC 152 乘积最大子数组

难度：中等
标签：动态规划

原题简述

返回连续子数组的最大乘积。

知识点介绍

负数会让最大值和最小值互换，所以同时维护当前最大乘积和最小乘积。

标准思路

遍历每个数，若 x 为负先交换 imax/imin，再更新。

最优标准解

python

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        imax = imin = ans = nums[0]
        for x in nums[1:]:
            if x < 0:                         # 遇到负数时，最大乘积和最小乘积交换角色
                imax, imin = imin, imax
            imax = max(x, imax * x)
            imin = min(x, imin * x)
            ans = max(ans, imax)              # 用当前位置结尾的最大和更新全局答案
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(1)。

易错点

负数要交换最大和最小；0 会自动重开。

多解补充

多解 1：暴力枚举

取舍说明： 能做但 O(n²)，不推荐。

python

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = nums[0]
        for i in range(len(nums)):
            prod = 1
            for j in range(i, len(nums)):
                prod *= nums[j]
                ans = max(ans, prod)          # 用当前位置结尾的最大和更新全局答案
        return ans                            # 返回最终答案

快速复习

最大乘积：同时维护最大/最小。

35. LC 155 最小栈

难度：中等
标签：栈、设计

原题简述

设计支持 push/pop/top/getMin 都为 O(1) 的栈。

知识点介绍

辅助栈同步记录当前最小值。

标准思路

每次 push 时把 min(x, 当前最小值) 压入 min_stack。

最优标准解

python

class MinStack:
    def __init__(self):
        self.stack = []                       # 栈保存还没结算的下标或状态
        self.min_stack = []                   # 栈保存还没结算的下标或状态

    def push(self, val: int) -> None:
        self.stack.append(val)                # 加入当前路径、节点或中间结果
        cur_min = val if not self.min_stack else min(val, self.min_stack[-1])  # 栈保存还没结算的下标或状态
        self.min_stack.append(cur_min)        # 加入当前路径、节点或中间结果

    def pop(self) -> None:
        self.stack.pop()                      # 弹出真实栈顶元素
        self.min_stack.pop()                  # 同步弹出这一层对应的最小值

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

复杂度

各操作 O(1)，空间 O(n)。

易错点

主栈和辅助栈要同步 push/pop。

多解补充

多解 1：辅助栈只存更小值

取舍说明： 空间可能更省，但 pop 逻辑要小心。

python

class MinStack:
    def __init__(self):
        self.stack = []                       # 栈保存还没结算的下标或状态
        self.min_stack = []                   # 栈保存还没结算的下标或状态

    def push(self, val: int) -> None:
        self.stack.append(val)                # 加入当前路径、节点或中间结果
        if not self.min_stack or val <= self.min_stack[-1]:  # 栈保存还没结算的下标或状态
            self.min_stack.append(val)        # 加入当前路径、节点或中间结果

    def pop(self) -> None:
        val = self.stack.pop()                # 栈保存还没结算的下标或状态
        if val == self.min_stack[-1]:         # 栈保存还没结算的下标或状态
            self.min_stack.pop()              # 同步弹出这一层对应的最小值

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

快速复习

最小栈：辅助栈存当前最小。

36. LC 198 打家劫舍

难度：中等
标签：动态规划

原题简述

不能偷相邻房屋，求最大金额。

知识点介绍

到第 i 间时，要么不偷它，要么偷它并加上 i-2 的最优值。

标准思路

用两个变量滚动表示前一间和前两间的最优值。

最优标准解

python

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2 = prev1 = 0                     # prev2 表示偷到前两间房时的最大金额
        for money in nums:
            cur = max(prev1, prev2 + money)   # 在不同选择中取收益最大的方案
            prev2, prev1 = prev1, cur         # prev2 表示偷到前两间房时的最大金额
        return prev1                          # prev1 表示偷到前一间房时的最大金额

复杂度

时间 O(n)，空间 O(1)。

易错点

状态是最大金额，不是当前是否偷。

多解补充

多解 1：DP 数组

取舍说明： 更直观但空间 O(n)。

python

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = [0] * (len(nums) + 1)            # 创建 DP 表，保存子问题答案
        for i, x in enumerate(nums, 1):
            dp[i] = max(dp[i-1], dp[i-2] + x)  # 创建 DP 表，保存子问题答案
        return dp[-1]

快速复习

打家劫舍：偷当前=前前+当前，不偷=前一。

37. LC 200 岛屿数量

难度：中等
标签：DFS、BFS、并查集

原题简述

网格中 1 表示陆地，0 表示水，返回岛屿个数。

知识点介绍

遇到一块未访问陆地，就用 DFS/BFS 把整座岛淹掉。

标准思路

遍历每个格子，遇到 1 就答案加一并把相连 1 改为 0。

最优标准解

python

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i, j):
            if i<0 or i>=m or j<0 or j>=n or grid[i][j] != '1':
                return                        # 结束当前递归分支
            grid[i][j] = '0'                  # 把当前陆地标为水，避免重复统计
            dfs(i+1,j)
            dfs(i-1,j)
            dfs(i,j+1)
            dfs(i,j-1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':         # 发现一块未访问陆地，说明找到一个新岛屿
                    ans += 1
                    dfs(i, j)
        return ans                            # 返回最终答案

复杂度

时间 O(mn)，空间 O(mn) 最坏递归栈。

易错点

访问后要标记，防止重复。

多解补充

多解 1：BFS

取舍说明： 避免递归过深。

python

from typing import List
from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m,n=len(grid),len(grid[0])
        ans=0
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    ans += 1
                    grid[i][j]='0'
                    q=deque([(i,j)])
                    while q:
                        x,y=q.popleft()
                        for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                            a,b=x+dx,y+dy
                            if 0<=a<m and 0<=b<n and grid[a][b]=='1':
                                grid[a][b]='0'
                                q.append((a,b))  # 加入当前路径、节点或中间结果
        return ans                            # 返回最终答案

快速复习

岛屿数量：发现陆地就淹掉整座岛。

38. LC 207 课程表

难度：中等
标签：图、拓扑排序

原题简述

给课程数和先修关系，判断能否完成所有课程。

知识点介绍

有向图有环则无法完成；拓扑排序可检测环。

标准思路

建立入度和邻接表，先学入度为 0 的课，逐步减少后续课程入度。

最优标准解

python

from typing import List
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]  # 建图：先修课指向依赖它的后续课程
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)                # 加入当前路径、节点或中间结果
            indeg[a] += 1
        q = deque([i for i in range(numCourses) if indeg[i] == 0])
        learned = 0
        while q:
            course = q.popleft()
            learned += 1
            for nxt in graph[course]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    q.append(nxt)             # 加入当前路径、节点或中间结果
        return learned == numCourses

复杂度

时间 O(V+E)，空间 O(V+E)。

易错点

边方向是 prerequisite -> course。

多解补充

多解 1：DFS 三色标记

取舍说明： 同样优秀，用递归检测有向环。

python

from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph=[[] for _ in range(numCourses)]  # 建图：先修课指向依赖它的后续课程
        for a,b in prerequisites: graph[b].append(a)  # 加入当前路径、节点或中间结果
        color=[0]*numCourses
        def dfs(u):
            if color[u]==1:
                return False                  # 当前情况不符合题意
            if color[u]==2:
                return True                   # 当前检查通过
            color[u]=1
            for v in graph[u]:
                if not dfs(v):
                    return False              # 当前情况不符合题意
            color[u]=2
            return True                       # 当前检查通过
        return all(dfs(i) for i in range(numCourses))

快速复习

课程表：拓扑排序判环。

39. LC 208 实现 Trie 前缀树

难度：中等
标签：设计、字典树

原题简述

实现插入单词、查找单词、查找前缀。

知识点介绍

Trie 用树结构按字符存储路径，节点需要 children 和 is_end。

标准思路

插入时沿字符创建节点；搜索时沿字符走，最后检查 is_end 或仅检查路径存在。

最优标准解

python

class TrieNode:
    def __init__(self):
        self.children = {}                    # children 保存当前节点到下一层字符节点的映射
        self.is_end = False                   # 标记是否有单词在当前节点结束

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:       # children 保存当前节点到下一层字符节点的映射
                node.children[ch] = TrieNode()  # children 保存当前节点到下一层字符节点的映射
            node = node.children[ch]          # children 保存当前节点到下一层字符节点的映射
        node.is_end = True                    # 标记是否有单词在当前节点结束

    def search(self, word: str) -> bool:
        node = self._find(word)
        return bool(node and node.is_end)     # 标记是否有单词在当前节点结束

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:       # children 保存当前节点到下一层字符节点的映射
                return None                   # 没有可返回的节点或结果
            node = node.children[ch]          # children 保存当前节点到下一层字符节点的映射
        return node                           # 返回当前构造出的节点

复杂度

操作时间 O(L)，空间与插入字符总数相关。

易错点

search 要检查 is_end；startsWith 不用。

多解补充

多解 1：嵌套字典

取舍说明： 代码更短，但结构不如节点类清晰。

python

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['#'] = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node:
                return False                  # 当前情况不符合题意
            node = node[ch]
        return '#' in node

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node:
                return False                  # 当前情况不符合题意
            node = node[ch]
        return True                           # 当前检查通过

快速复习

Trie：按字符建树。

40. LC 215 数组中的第 K 个最大元素

难度：中等
标签：堆、快速选择

原题简述

返回数组中第 k 大元素。

知识点介绍

小根堆维护 k 个最大元素，堆顶就是第 k 大；快速选择平均 O(n)。

标准思路

遍历元素压入小根堆，堆大小超过 k 就弹出最小。

最优标准解

python

from typing import List
import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []                             # 堆用来维护当前最有价值的 k 个元素
        for x in nums:
            heapq.heappush(heap, x)           # 把当前候选放入堆
            if len(heap) > k:
                heapq.heappop(heap)           # 堆大小超过 k 时，弹出优先级最低的元素
        return heap[0]

复杂度

时间 O(n log k)，空间 O(k)。

易错点

维护的是 k 个最大，不是全量排序。

多解补充

多解 1：排序

取舍说明： 最简单但 O(n log n)。

python

from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)               # 排序后方便利用有序性
        return nums[k - 1]

快速复习

第 K 大：小根堆大小 k。

41. LC 221 最大正方形

难度：中等
标签：动态规划、矩阵

原题简述

在 0/1 矩阵中找到只含 1 的最大正方形面积。

知识点介绍

dp[i][j] 表示以该格为右下角的最大正方形边长。

标准思路

若当前为 1，边长由上、左、左上三者最小值 +1 决定。

最优标准解

python

from typing import List

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0]*(n+1) for _ in range(m+1)]  # 创建 DP 表，保存子问题答案
        best = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if matrix[i-1][j-1] == '1':
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1  # 创建 DP 表，保存子问题答案
                    best = max(best, dp[i][j])  # 创建 DP 表，保存子问题答案
        return best * best

复杂度

时间 O(mn)，空间 O(mn)。

易错点

返回面积不是边长；边界可用多一行一列简化。

多解补充

多解 1：空间压缩

取舍说明： 同样优秀，把空间降到 O(n)。

python

from typing import List

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m,n=len(matrix),len(matrix[0])
        dp=[0]*(n+1)                          # 创建 DP 表，保存子问题答案
        best=prev=0
        for i in range(1,m+1):
            prev=0
            for j in range(1,n+1):
                tmp=dp[j]                     # 创建 DP 表，保存子问题答案
                if matrix[i-1][j-1]=='1':
                    dp[j]=min(dp[j],dp[j-1],prev)+1  # 创建 DP 表，保存子问题答案
                    best=max(best,dp[j])      # 创建 DP 表，保存子问题答案
                else:
                    dp[j]=0                   # 创建 DP 表，保存子问题答案
                prev=tmp
        return best*best

快速复习

最大正方形：右下角 DP。

42. LC 236 二叉树的最近公共祖先

难度：中等
标签：树、DFS

原题简述

给定二叉树和两个节点，返回最近公共祖先。

知识点介绍

如果一个节点的左右子树分别找到 p 和 q，则该节点就是 LCA。

标准思路

递归返回当前子树中是否找到 p/q；左右都非空返回 root。

最优标准解

python

from typing import Optional

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root is p or root is q:
            return root                       # 返回处理后的根节点
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root                       # 返回处理后的根节点
        return left if left else right

复杂度

时间 O(n)，空间 O(h)。

易错点

不是 BST，不能用大小关系；比较节点对象。

多解补充

多解 1：父指针集合

取舍说明： 需要额外空间，思路直观。

python

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        parent = {root: None}
        stack = [root]
        while p not in parent or q not in parent:
            node = stack.pop()
            if node.left:
                parent[node.left]=node
                stack.append(node.left)       # 加入当前路径、节点或中间结果
            if node.right:
                parent[node.right]=node
                stack.append(node.right)      # 加入当前路径、节点或中间结果
        seen=set()
        while p:
            seen.add(p)
            p=parent[p]
        while q not in seen:
            q=parent[q]
        return q

快速复习

LCA：左右都找到则当前是祖先。

43. LC 238 除自身以外数组的乘积

难度：中等
标签：数组、前缀积

原题简述

返回每个位置除自身外其余元素乘积，不能用除法。

知识点介绍

某位置答案=左边所有数乘积*右边所有数乘积。

标准思路

先从左到右存左乘积，再从右到左乘上右乘积。

最优标准解

python

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n=len(nums)
        ans=[1]*n
        left=1
        for i in range(n):
            ans[i]=left
            left*=nums[i]
        right=1
        for i in range(n-1,-1,-1):
            ans[i]*=right
            right*=nums[i]
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(1) 不算返回数组。

易错点

不能把返回数组算作额外空间；左右乘积初始为 1。

多解补充

多解 1：左右数组

取舍说明： 更直观但空间 O(n)。

python

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n=len(nums)
        left=[1]*n
        right=[1]*n
        for i in range(1,n): left[i]=left[i-1]*nums[i-1]
        for i in range(n-2,-1,-1): right[i]=right[i+1]*nums[i+1]
        return [left[i]*right[i] for i in range(n)]

快速复习

除自身乘积：左积 * 右积。

44. LC 240 搜索二维矩阵 II

难度：中等
标签：矩阵、二分、双指针

原题简述

矩阵每行每列升序，判断 target 是否存在。

知识点介绍

从右上角开始：左边更小，下面更大，能单调排除一行或一列。

标准思路

若当前大于 target 左移；小于 target 下移。

最优标准解

python

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m,n=len(matrix),len(matrix[0])
        i,j=0,n-1
        while i<m and j>=0:
            if matrix[i][j]==target:
                return True                   # 当前检查通过
            if matrix[i][j]>target:
                j-=1
            else:
                i+=1
        return False                          # 当前情况不符合题意

复杂度

时间 O(m+n)，空间 O(1)。

易错点

从右上或左下开始才有单调排除效果。

多解补充

多解 1：每行二分

取舍说明： 可做但 O(m log n)。

python

from typing import List
import bisect

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            idx=bisect.bisect_left(row,target)
            if idx<len(row) and row[idx]==target:
                return True                   # 当前检查通过
        return False                          # 当前情况不符合题意

快速复习

二维搜索：右上角走楼梯。

45. LC 279 完全平方数

难度：中等
标签：动态规划、BFS

原题简述

给定 n，求和为 n 的完全平方数最少数量。

知识点介绍

完全背包：平方数可重复使用。

标准思路

dp[i] 表示凑成 i 的最少平方数个数。

最优标准解

python

class Solution:
    def numSquares(self, n: int) -> int:
        squares=[i*i for i in range(1,int(n**0.5)+1)]
        dp=[0]+[float('inf')]*n               # 创建 DP 表，保存子问题答案
        for i in range(1,n+1):
            for s in squares:
                if s>i:
                    break
                dp[i]=min(dp[i],dp[i-s]+1)    # 创建 DP 表，保存子问题答案
        return dp[n]

复杂度

时间 O(n√n)，空间 O(n)。

易错点

dp[0]=0；平方数可重复用。

多解补充

多解 1：BFS

取舍说明： 按层表示使用几个平方数，第一次到 n 即最少。

python

from collections import deque

class Solution:
    def numSquares(self, n: int) -> int:
        squares=[i*i for i in range(1,int(n**0.5)+1)]
        q=deque([(0,0)])
        seen={0}
        while q:
            cur,step=q.popleft()
            for s in squares:
                nxt=cur+s
                if nxt==n:
                    return step+1
                if nxt<n and nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt,step+1))    # 加入当前路径、节点或中间结果

快速复习

完全平方数：完全背包 DP。

46. LC 287 寻找重复数

难度：中等
标签：数组、双指针、二分

原题简述

长度 n+1，数字在 1..n，只有一个重复数，不能改数组。

知识点介绍

把 nums[i] 看成指针 i->nums[i]，重复数对应环入口。

标准思路

Floyd 判环后找入口。

最优标准解

python

from typing import List

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow=fast=nums[0]
        while True:
            slow=nums[slow]
            fast=nums[nums[fast]]
            if slow==fast:
                break
        p=nums[0]
        while p!=slow:
            p=nums[p]
            slow=nums[slow]
        return p

复杂度

时间 O(n)，空间 O(1)。

易错点

这是数组上的环，不是链表节点；初始化和移动方式要一致。

多解补充

多解 1：二分计数

取舍说明： 不改数组，O(n log n)。

python

from typing import List

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left,right=1,len(nums)-1
        while left<right:
            mid=(left+right)//2
            cnt=sum(x<=mid for x in nums)
            if cnt>mid:
                right=mid
            else:
                left=mid+1
        return left

快速复习

重复数：数组映射成环入口。

47. LC 300 最长递增子序列

难度：中等
标签：动态规划、二分

原题简述

返回最长严格递增子序列长度。

知识点介绍

tails[len] 保存长度为 len+1 的递增子序列的最小结尾。

标准思路

每个数用二分替换第一个 >= 它的位置。

最优标准解

python

from typing import List
import bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails=[]
        for x in nums:
            i=bisect.bisect_left(tails,x)
            if i==len(tails):
                tails.append(x)               # 加入当前路径、节点或中间结果
            else:
                tails[i]=x
        return len(tails)

复杂度

时间 O(n log n)，空间 O(n)。

易错点

tails 不是实际 LIS，只保存最优结尾。

多解补充

多解 1：O(n²) DP

取舍说明： 更直观，但大数据较慢。

python

from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp=[1]*len(nums)                      # 创建 DP 表，保存子问题答案
        for i in range(len(nums)):
            for j in range(i):
                if nums[j]<nums[i]:
                    dp[i]=max(dp[i],dp[j]+1)  # 创建 DP 表，保存子问题答案
        return max(dp)                        # 在不同选择中取收益最大的方案

快速复习

LIS：二分维护最小结尾。

48. LC 309 最佳买卖股票时机含冷冻期

难度：中等
标签：动态规划

原题简述

卖出股票后第二天不能买入，求最大利润。

知识点介绍

每天状态：持有、空仓且可买、空仓且冷冻。

标准思路

状态转移时卖出进入冷冻，冷冻下一天变为可买。

最优标准解

python

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        hold=-prices[0]                       # hold 表示当天结束后手里持有股票的最大利润
        free=0
        cool=0
        for p in prices[1:]:
            new_hold=max(hold, free-p)        # hold 表示当天结束后手里持有股票的最大利润
            new_free=max(free, cool)
            new_cool=hold+p                   # hold 表示当天结束后手里持有股票的最大利润
            hold,free,cool=new_hold,new_free,new_cool  # hold 表示当天结束后手里持有股票的最大利润
        return max(free,cool)

复杂度

时间 O(n)，空间 O(1)。

易错点

买入只能从 free 来，不能从 cool 来。

多解补充

多解 1：DP 数组

取舍说明： 更直观但空间 O(n)。

python

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n=len(prices)
        hold=[0]*n                            # hold 表示当天结束后手里持有股票的最大利润
        free=[0]*n
        cool=[0]*n
        hold[0]=-prices[0]                    # hold 表示当天结束后手里持有股票的最大利润
        for i in range(1,n):
            hold[i]=max(hold[i-1],free[i-1]-prices[i])  # hold 表示当天结束后手里持有股票的最大利润
            free[i]=max(free[i-1],cool[i-1])
            cool[i]=hold[i-1]+prices[i]       # hold 表示当天结束后手里持有股票的最大利润
        return max(free[-1],cool[-1])

快速复习

股票冷冻期：hold/free/cool 三状态。

49. LC 322 零钱兑换

难度：中等
标签：动态规划、完全背包

原题简述

给定硬币面额和总金额，求最少硬币数，不可达返回 -1。

知识点介绍

完全背包最少数量：硬币可重复使用。

标准思路

dp[x] 表示凑成金额 x 的最少硬币数。

最优标准解

python

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[float('inf')]*(amount+1)          # 创建 DP 表，保存子问题答案
        dp[0]=0                               # 创建 DP 表，保存子问题答案
        for x in range(1,amount+1):
            for c in coins:
                if x>=c:
                    dp[x]=min(dp[x],dp[x-c]+1)  # 创建 DP 表，保存子问题答案
        return -1 if dp[amount]==float('inf') else dp[amount]  # 创建 DP 表，保存子问题答案

复杂度

时间 O(amount·len(coins))，空间 O(amount)。

易错点

不可达要返回 -1；dp[0]=0。

多解补充

多解 1：BFS

取舍说明： 按硬币数层层扩展，首次到达 amount 最少。

python

from typing import List
from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        q=deque([(0,0)])
        seen={0}
        while q:
            cur,step=q.popleft()
            if cur==amount:
                return step
            for c in coins:
                nxt=cur+c
                if nxt<=amount and nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt,step+1))    # 加入当前路径、节点或中间结果
        return -1

快速复习

零钱兑换：完全背包最少数。

50. LC 337 打家劫舍 III

难度：中等
标签：树形 DP

原题简述

二叉树上不能偷直接相连的两个节点，求最大金额。

知识点介绍

每个节点有两个状态：偷当前、不偷当前。

标准思路

递归返回 (not_rob, rob)。偷当前则孩子不能偷；不偷当前则孩子可偷可不偷。

最优标准解

python

from typing import Optional

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return (0,0)
            l0,l1=dfs(node.left)
            r0,r1=dfs(node.right)
            rob=node.val+l0+r0
            not_rob=max(l0,l1)+max(r0,r1)     # 在不同选择中取收益最大的方案
            return (not_rob, rob)
        return max(dfs(root))                 # 在不同选择中取收益最大的方案

复杂度

时间 O(n)，空间 O(h)。

易错点

不能简单隔层相加；每个节点都要两个状态。

多解补充

多解 1：记忆化递归

取舍说明： 也能做，但状态不如二元返回清晰。

python

from typing import Optional

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        memo={}
        def f(node):
            if not node:
                return 0
            if node in memo:
                return memo[node]
            take=node.val
            if node.left:
                take += f(node.left.left)+f(node.left.right)
            if node.right:
                take += f(node.right.left)+f(node.right.right)
            skip=f(node.left)+f(node.right)
            memo[node]=max(take,skip)         # 在不同选择中取收益最大的方案
            return memo[node]
        return f(root)

快速复习

树上打劫：返回偷/不偷。

51. LC 347 前 K 个高频元素

难度：中等
标签：哈希表、堆、桶排序

原题简述

返回出现频率最高的 k 个元素。

知识点介绍

先计数，再用堆或桶按频率取前 k。

标准思路

用小根堆维护 k 个最高频元素。

最优标准解

python

from typing import List
from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count=Counter(nums)                   # 统计每个元素出现次数
        heap=[]                               # 堆用来维护当前最有价值的 k 个元素
        for num,freq in count.items():
            heapq.heappush(heap,(freq,num))   # 把当前候选放入堆
            if len(heap)>k:
                heapq.heappop(heap)           # 堆大小超过 k 时，弹出优先级最低的元素
        return [num for freq,num in heap]

复杂度

时间 O(n log k)，空间 O(n)。

易错点

堆里放频率；返回顺序不限。

多解补充

多解 1：桶排序

取舍说明： 同样优秀，频率最大不超过 n。

python

from typing import List
from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count=Counter(nums)                   # 统计每个元素出现次数
        buckets=[[] for _ in range(len(nums)+1)]
        for num,freq in count.items(): buckets[freq].append(num)  # 加入当前路径、节点或中间结果
        ans=[]
        for f in range(len(buckets)-1,0,-1):
            for num in buckets[f]:
                ans.append(num)
                if len(ans)==k:
                    return ans                # 返回最终答案

快速复习

Top K 高频：计数 + 小根堆。

52. LC 394 字符串解码

难度：中等
标签：栈、字符串

原题简述

解码形如 k[encoded] 的字符串，支持嵌套。

知识点介绍

遇到 '[' 时保存当前字符串和重复次数，遇到 ']' 时弹出并拼接。

标准思路

num 负责读多位数字，cur 负责当前层字符串。

最优标准解

python

class Solution:
    def decodeString(self, s: str) -> str:
        stack=[]
        cur=''
        num=0
        for ch in s:
            if ch.isdigit():
                num=num*10+int(ch)
            elif ch=='[':
                stack.append((cur,num))       # 加入当前路径、节点或中间结果
                cur=''
                num=0
            elif ch==']':
                prev,k=stack.pop()
                cur=prev+cur*k
            else:
                cur+=ch
        return cur

复杂度

时间 O(输出长度)，空间 O(嵌套深度+输出长度)。

易错点

数字可能多位；嵌套要用栈。

多解补充

多解 1：递归解析

取舍说明： 同样正确，但索引管理更难。

python

class Solution:
    def decodeString(self, s: str) -> str:
        def dfs(i):
            res=''
            num=0
            while i<len(s):
                ch=s[i]
                if ch.isdigit():
                    num=num*10+int(ch)
                elif ch=='[':
                    sub,i=dfs(i+1)
                    res+=sub*num
                    num=0
                elif ch==']':
                    return res,i
                else:
                    res+=ch
                i+=1
            return res,i
        return dfs(0)[0]

快速复习

解码字符串：栈保存上一层。

53. LC 399 除法求值

难度：中等
标签：图、DFS、并查集

原题简述

给变量除法关系和查询，返回查询结果。

知识点介绍

a/b=value 可看成有权图边 a->b=value，b->a=1/value。

标准思路

对每个查询从起点 DFS 到终点，沿途乘权重。

最优标准解

python

from typing import List
from collections import defaultdict

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph=defaultdict(list)
        for (a,b),v in zip(equations,values):
            graph[a].append((b,v))            # 加入当前路径、节点或中间结果
            graph[b].append((a,1/v))          # 加入当前路径、节点或中间结果
        def dfs(a,b,seen):
            if a not in graph or b not in graph:
                return -1.0
            if a==b:
                return 1.0
            seen.add(a)
            for nxt,w in graph[a]:
                if nxt not in seen:
                    res=dfs(nxt,b,seen)
                    if res!=-1.0:
                        return w*res
            return -1.0
        return [dfs(a,b,set()) for a,b in queries]

复杂度

建图 O(E)，每次查询最坏 O(V+E)。空间 O(V+E)。

易错点

要加反向边；不存在变量返回 -1。

多解补充

多解 1：Floyd

取舍说明： 查询多时可预处理所有比值，但空间 O(V²)。

python

from typing import List
from collections import defaultdict

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        dist=defaultdict(dict)
        for (a,b),v in zip(equations,values):
            dist[a][a]=dist[b][b]=1.0
            dist[a][b]=v
            dist[b][a]=1/v
        for k in list(dist):
            for i in list(dist):
                for j in list(dist):
                    if k in dist[i] and j in dist[k]:
                        dist[i][j]=dist[i][k]*dist[k][j]
        return [dist[a].get(b,-1.0) for a,b in queries]

快速复习

除法求值：有权图路径乘积。

54. LC 406 根据身高重建队列

难度：中等
标签：贪心、排序

原题简述

每个人 [h,k] 表示前面身高>=h 的人数为 k，重建队列。

知识点介绍

先放高个子，矮个子不会影响高个子的 k。

标准思路

按身高降序、k 升序排序，然后按 k 下标插入。

最优标准解

python

from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))  # 排序后方便利用有序性
        ans=[]
        for p in people:
            ans.insert(p[1], p)
        return ans                            # 返回最终答案

复杂度

时间 O(n²)，空间 O(n)。

易错点

排序规则必须是身高降序、k 升序。

多解补充

多解 1：反向思路

取舍说明： 低个先放需要空位统计，代码复杂。

python

from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x:(x[0],-x[1]))  # 排序后方便利用有序性
        ans=[None]*len(people)
        for h,k in people:
            spaces=k+1
            for i in range(len(ans)):
                if ans[i] is None:
                    spaces-=1
                    if spaces==0:
                        ans[i]=[h,k]
                        break
        return ans                            # 返回最终答案

快速复习

重建队列：高个先插。

55. LC 416 分割等和子集

难度：中等
标签：动态规划、背包

原题简述

判断数组能否分成两个和相等的子集。

知识点介绍

总和必须为偶数；问题转成能否选若干数凑出 sum/2。

标准思路

0/1 背包，用 dp[j] 表示是否能凑出 j，倒序更新。

最优标准解

python

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total=sum(nums)
        if total%2:
            return False                      # 当前情况不符合题意
        target=total//2
        dp=[False]*(target+1)                 # 创建 DP 表，保存子问题答案
        dp[0]=True                            # 创建 DP 表，保存子问题答案
        for x in nums:
            for j in range(target,x-1,-1):
                dp[j]=dp[j] or dp[j-x]        # 创建 DP 表，保存子问题答案
        return dp[target]

复杂度

时间 O(n·target)，空间 O(target)。

易错点

0/1 背包要倒序；总和奇数直接 False。

多解补充

多解 1：集合滚动

取舍说明： 写法直观，但空间也可能较大。

python

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s=sum(nums)
        if s%2:
            return False                      # 当前情况不符合题意
        target=s//2
        possible={0}
        for x in nums:
            possible |= {v+x for v in possible if v+x<=target}
        return target in possible

快速复习

等和分割：0/1 背包凑半和。

56. LC 437 路径总和 III

难度：中等
标签：树、前缀和、DFS

原题简述

统计二叉树中路径和等于 targetSum 的路径数量，路径向下即可，不必从根开始。

知识点介绍

树上前缀和：当前前缀 curr，若之前有 curr-target，则中间路径和为 target。

标准思路

DFS 时维护前缀和出现次数，回溯离开节点时撤销当前前缀。

最优标准解

python

from typing import Optional
from collections import defaultdict

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        count=defaultdict(int)
        count[0]=1
        ans=0
        def dfs(node, cur):
            nonlocal ans
            if not node:                      # 空节点是递归边界
                return                        # 结束当前递归分支
            cur += node.val
            ans += count[cur-targetSum]
            count[cur] += 1
            dfs(node.left, cur)
            dfs(node.right, cur)
            count[cur] -= 1
        dfs(root,0)
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(h) 到 O(n)。

易错点

回溯时必须 count[cur]-=1；路径只向下。

多解补充

多解 1：从每个节点向下 DFS

取舍说明： 直观但最坏 O(n²)。

python

from typing import Optional

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def from_node(node, remain):
            if not node:                      # 空节点是递归边界
                return 0
            return (node.val==remain)+from_node(node.left,remain-node.val)+from_node(node.right,remain-node.val)
        if not root:
            return 0
        return from_node(root,targetSum)+self.pathSum(root.left,targetSum)+self.pathSum(root.right,targetSum)

快速复习

路径总和 III：树上前缀和。

57. LC 438 找到字符串中所有字母异位词

难度：中等
标签：滑动窗口、哈希表

原题简述

返回 s 中所有 p 的异位词起始下标。

知识点介绍

固定长度窗口，比较窗口字符计数和 p 的计数。

标准思路

用 need/window 计数，窗口长度超过 p 时移出左端。

最优标准解

python

from typing import List
from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        need=Counter(p)
        window=Counter()
        ans=[]
        m=len(p)
        for i,ch in enumerate(s):
            window[ch]+=1
            if i>=m:
                left=s[i-m]
                window[left]-=1
                if window[left]==0:
                    del window[left]
            if window==need:
                ans.append(i-m+1)
        return ans                            # 返回最终答案

复杂度

时间 O(n·字符集比较)，空间 O(字符集)。小写字母可视为 O(n)。

易错点

窗口长度固定为 len(p)。

多解补充

多解 1：数组计数

取舍说明： 只含小写字母时更快。

python

from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p)>len(s):
            return []
        need=[0]*26
        win=[0]*26
        for ch in p: need[ord(ch)-97]+=1
        ans=[]
        m=len(p)
        for i,ch in enumerate(s):
            win[ord(ch)-97]+=1
            if i>=m:
                win[ord(s[i-m])-97]-=1
            if win==need:
                ans.append(i-m+1)
        return ans                            # 返回最终答案

快速复习

异位词索引：固定窗口计数。

58. LC 494 目标和

难度：中等
标签：动态规划、背包

原题简述

给每个数加 + 或 -，求表达式结果为 target 的方案数。

知识点介绍

设正数和为 P，总和 S，则 P-(S-P)=target，转成子集和 P=(S+target)/2。

标准思路

用 0/1 背包计数 dp[j] 表示凑出 j 的方案数。

最优标准解

python

from typing import List

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s=sum(nums)
        if abs(target)>s or (s+target)%2:
            return 0
        bag=(s+target)//2
        dp=[0]*(bag+1)                        # 创建 DP 表，保存子问题答案
        dp[0]=1                               # 创建 DP 表，保存子问题答案
        for x in nums:
            for j in range(bag,x-1,-1):
                dp[j]+=dp[j-x]                # 创建 DP 表，保存子问题答案
        return dp[bag]

复杂度

时间 O(n·bag)，空间 O(bag)。

易错点

奇偶不匹配直接 0；计数背包要累加。

多解补充

多解 1：DFS 记忆化

取舍说明： 直观但状态数可能较多。

python

from typing import List
from functools import lru_cache

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        @lru_cache(None)
        def dfs(i,total):
            if i==len(nums):
                return 1 if total==target else 0
            return dfs(i+1,total+nums[i])+dfs(i+1,total-nums[i])
        return dfs(0,0)

快速复习

目标和：转子集和计数。

59. LC 538 把二叉搜索树转换为累加树

难度：中等
标签：树、反向中序

原题简述

将 BST 每个节点值变为原树中大于等于它的节点值之和。

知识点介绍

BST 中序升序，反向中序就是从大到小遍历。

标准思路

维护累计和 total，按右根左顺序更新节点值。

最优标准解

python

from typing import Optional

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        total=0
        def dfs(node):
            nonlocal total
            if not node:
                return                        # 结束当前递归分支
            dfs(node.right)
            total += node.val
            node.val = total
            dfs(node.left)
        dfs(root)
        return root                           # 返回处理后的根节点

复杂度

时间 O(n)，空间 O(h)。

易错点

遍历顺序是右根左，不是普通中序。

多解补充

多解 1：迭代栈

取舍说明： 同样正确，避免递归。

python

from typing import Optional

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        total=0
        stack=[]
        cur=root
        while cur or stack:
            while cur:
                stack.append(cur)             # 加入当前路径、节点或中间结果
                cur=cur.right
            cur=stack.pop()
            total+=cur.val
            cur.val=total
            cur=cur.left
        return root                           # 返回处理后的根节点

快速复习

累加树：反向中序累计。

60. LC 560 和为 K 的子数组

难度：中等
标签：前缀和、哈希表

原题简述

统计连续子数组和等于 k 的数量。

知识点介绍

若当前前缀和为 cur，之前出现过 cur-k，则中间子数组和为 k。

标准思路

遍历时边统计边更新前缀和次数。

最优标准解

python

from typing import List
from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count=defaultdict(int)
        count[0]=1
        cur=ans=0
        for x in nums:
            cur += x
            ans += count[cur-k]
            count[cur] += 1
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(n)。

易错点

不能用滑动窗口，因为有负数；count[0]=1。

多解补充

多解 1：暴力前缀枚举

取舍说明： 能做但 O(n²)。

python

from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans=0
        for i in range(len(nums)):
            s=0
            for j in range(i,len(nums)):
                s+=nums[j]
                if s==k:
                    ans+=1
        return ans                            # 返回最终答案

快速复习

子数组和 K：前缀和 + 哈希。

61. LC 581 最短无序连续子数组

难度：中等
标签：数组、排序、双指针

原题简述

找到最短连续子数组，排序它后整个数组有序。

知识点介绍

从左到右找右边界：只要当前数小于历史最大值，说明它应在无序段内。反向找左边界。

标准思路

维护前缀最大和后缀最小。

最优标准解

python

from typing import List

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n=len(nums)
        right=-1
        max_seen=float('-inf')
        for i,x in enumerate(nums):
            if x<max_seen:
                right=i
            else:
                max_seen=x
        left=n
        min_seen=float('inf')
        for i in range(n-1,-1,-1):
            if nums[i]>min_seen:
                left=i
            else:
                min_seen=nums[i]
        return 0 if right==-1 else right-left+1

复杂度

时间 O(n)，空间 O(1)。

易错点

已经有序时返回 0。

多解补充

多解 1：排序比较

取舍说明： 简单但 O(n log n)。

python

from typing import List

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        sorted_nums=sorted(nums)
        l=0
        while l<len(nums) and nums[l]==sorted_nums[l]:
            l+=1
        r=len(nums)-1
        while r>=0 and nums[r]==sorted_nums[r]:
            r-=1
        return 0 if l>=r else r-l+1

快速复习

最短无序段：正扫定右界，反扫定左界。

62. LC 621 任务调度器

难度：中等
标签：贪心、计数

原题简述

相同任务之间至少间隔 n，求完成所有任务最短时间。

知识点介绍

最频繁任务决定框架长度。

标准思路

若最大频率为 maxf，有 cnt 个任务达到 maxf，最短为 max((maxf-1)*(n+1)+cnt, 总任务数)。

最优标准解

python

from typing import List
from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq=Counter(tasks).values()
        maxf=max(freq)
        cnt=sum(1 for f in freq if f==maxf)
        return max(len(tasks), (maxf-1)*(n+1)+cnt)

复杂度

时间 O(T)，空间 O(字符集)。

易错点

最后一组不需要完整冷却；要和任务总数取 max。

多解补充

多解 1：堆模拟

取舍说明： 通用但复杂度更高。

python

from typing import List
from collections import Counter, deque
import heapq

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        heap=[-c for c in Counter(tasks).values()]
        heapq.heapify(heap)
        wait=deque()
        time=0
        while heap or wait:
            time+=1
            if heap:
                c=heapq.heappop(heap)+1
                if c:
                    wait.append((time+n,c))   # 加入当前路径、节点或中间结果
            if wait and wait[0][0]==time:
                heapq.heappush(heap, wait.popleft()[1])
        return time

快速复习

任务调度：最高频任务搭框架。

63. LC 647 回文子串

难度：中等
标签：字符串、中心扩展、DP

原题简述

统计字符串中所有回文子串数量。

知识点介绍

每个回文都有中心，奇数和偶数中心都要统计。

标准思路

对每个中心向两边扩，扩成功一次就计数加一。

最优标准解

python

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans=0
        def expand(l,r):
            nonlocal ans
            while l>=0 and r<len(s) and s[l]==s[r]:
                ans+=1
                l-=1
                r+=1
        for i in range(len(s)):
            expand(i,i)
            expand(i,i+1)
        return ans                            # 返回最终答案

复杂度

时间 O(n²)，空间 O(1)。

易错点

偶数中心不能漏。

多解补充

多解 1：DP

取舍说明： 可做但空间 O(n²)。

python

class Solution:
    def countSubstrings(self, s: str) -> int:
        n=len(s)
        dp=[[False]*n for _ in range(n)]
        ans=0
        for length in range(1,n+1):
            for i in range(n-length+1):
                j=i+length-1
                if s[i]==s[j] and (length<=2 or dp[i+1][j-1]):
                    dp[i][j]=True
                    ans+=1
        return ans                            # 返回最终答案

快速复习

回文子串：中心扩展计数。

64. LC 739 每日温度

难度：中等
标签：单调栈

原题简述

对每天温度，返回还要等几天才有更高温度。

知识点介绍

单调栈存还没找到更高温的下标，栈内温度递减。

标准思路

当前温度比栈顶高时，栈顶那天的答案就是当前下标差。

最优标准解

python

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        ans=[0]*len(temperatures)
        stack=[]                              # 栈保存还没结算的下标或状态
        for i,t in enumerate(temperatures):
            while stack and t>temperatures[stack[-1]]:  # 单调栈保存还没找到更高温度的日期下标
                j=stack.pop()                 # 栈保存还没结算的下标或状态
                ans[j]=i-j
            stack.append(i)                   # 加入当前路径、节点或中间结果
        return ans                            # 返回最终答案

复杂度

时间 O(n)，空间 O(n)。

易错点

栈里存下标，不是温度；条件是当前温度更高。

多解补充

多解 1：暴力枚举

取舍说明： 能做但 O(n²)。

python

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        ans=[0]*len(temperatures)
        for i in range(len(temperatures)):
            for j in range(i+1,len(temperatures)):
                if temperatures[j]>temperatures[i]:
                    ans[i]=j-i
                    break
        return ans                            # 返回最终答案

快速复习

每日温度：单调递减栈。

LeetCode HOT100 中等题详细学习版

目录

1. LC 2 两数相加

原题简述

知识点介绍

标准思路

最优标准解

复杂度

易错点

多解补充

多解 1：递归

快速复习

2. LC 3 无重复字符的最长子串

原题简述

知识点介绍

标准思路

最优标准解

复杂度

易错点

多解补充

多解 1：set 窗口

快速复习

3. LC 5 最长回文子串

原题简述

知识点介绍

标准思路

最优标准解

复杂度

易错点

多解补充

多解 1：动态规划

快速复习

4. LC 11 盛最多水的容器

原题简述

知识点介绍

标准思路

最优标准解

复杂度

易错点

多解补充

多解 1：暴力枚举

快速复习

5. LC 15 三数之和

原题简述

知识点介绍

标准思路

最优标准解

复杂度

易错点

多解补充

多解 1：哈希两数之和思路

快速复习

6. LC 17 电话号码的字母组合

原题简述

知识点介绍

标准思路

最优标准解

复杂度

易错点

多解补充

多解 1：队列迭代

快速复习

7. LC 19 删除链表的倒数第 N 个结点

原题简述

知识点介绍

标准思路

最优标准解

复杂度

易错点

多解补充

多解 1：两遍扫描

快速复习

8. LC 22 括号生成

原题简述

知识点介绍

标准思路

最优标准解

复杂度

易错点

多解补充