Skip to content
All notes

Hot100 常见题目解法速记

速记 Hot100 常见题目的核心解法、复杂度和实现边界。

Hot100 常见题目解法速记

[!info] 目的 记录 Hot100 常见题目的核心解法、关键边界和实现抓手，方便刷题时快速回忆。

题目速记

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

  • 解法：滑动窗口。
  • 核心：一次遍历中同时调整左右指针，把 O(n^2) 降到 O(n)。
  • 思路：窗口可以看成一个队列。以 abcabcbb 为例，窗口先扩张到 abc；当再进入 a 变成 abca 时，不再满足“无重复”条件。此时持续移出左端字符，直到窗口重新合法。
  • 复用场景：这类“维护一个满足条件的连续子串/子数组”的题都适合滑动窗口，例如 209. 长度最小的子数组。

25. K 个一组翻转链表

  • 解法：先分组，再组内翻转。
  • 核心：这题重点不在复杂算法，而在链表指针设计和边界处理。
  • 步骤 1：先分组。head 指向每组头节点，tail 从 head 出发向后走 k-1 步；pre 是组前一个节点，next 是组后一个节点。
  • 步骤 2：翻转组内链表。保留当前节点的 next 指针，再把当前节点指向前驱；翻转后新头尾就是原来的尾头互换。
  • 步骤 3：重新拼接头尾并设置新的 head。把上一组尾巴接到当前组新头，再把当前组新尾接到下一组。

206. 反转链表

  • 解法：迭代翻转。
  • 核心：保留当前节点的 next，然后把当前节点的 next 指向 pre；之后分别推进 pre 和 p。

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

  • 解法 1：先快排，再返回第 k 个位置。
  • 快排核心：分治思想，流程是划分、递归解决左右子区间。partition 会选择一个元素 x，使其左边都小于 x，右边都大于 x，于是 x 的位置 q 就说明它是第 q 小元素。
  • 解法 2：快速选择。
  • 核心：对快排做改造，只递归一边。若 q == n-k，直接返回；若 n-k < q，去左区间递归；否则去右区间递归。这样把两次递归降成一次，平均复杂度为 O(n)。

103. 二叉树的锯齿形层次遍历

  • 解法：层次遍历。
  • 核心：遍历时照常把左右孩子加入队列，但按层收集节点值；输出某一层时，根据标记决定是否反转。
  • 实现抓手：可以额外存储节点深度，或者直接按层循环；每层结束时根据 flag 决定是否反转，然后切换 flag = 1 - flag。

200. 岛屿数量

  • 解法：图上的 DFS。
  • 核心：岛屿系列本质上是“遍历整张网格，遇到一块新陆地就做一次 DFS/BFS 抹掉整块区域”。
  • DFS 模板：先处理越界和非法情况，再递归访问上下左右四个方向。
  • 去重方式：访问过的格子直接改成 0，避免重复遍历。
  • 结论：答案就是触发 DFS 的次数。
  • 注意：LeetCode 里网格值通常是字符串，判断时要写成 '1'。

15. 三数之和

  • 解法：排序 + 双指针。
  • 核心：先排序，再固定 i，令 L = i + 1，R = n - 1，通过双指针单边收缩降低时间复杂度。
  • 移动规则：若 nums[i] + nums[L] + nums[R] > 0，则 R--；若小于 0，则 L++；若等于 0，记录答案并跳过重复元素。
  • 注意：固定点和双指针两侧都要做去重。

160. 相交链表

  • 解法：双指针补齐长度差。
  • 核心：链表 A 长度是 a + c，链表 B 长度是 b + c。要消除长度差，最直接的方法就是让两个指针都走完 a + b + c 这段总路程。
  • 做法：PA 走完 A 后跳到 B 的头，PB 走完 B 后跳到 A 的头。
  • 结论：当 PA == PB 时，要么相遇在交点，要么都为 nil。

146. LRU 缓存机制

  • 解法：哈希表 + 双向链表。
  • 核心：哈希表负责 O(1) 定位节点，双向链表负责维护“最近使用顺序”。
  • 约定：链表头表示最近使用，链表尾表示最久未使用。
  • get：找到节点后把它移动到头部，再返回值。
  • put：若 key 已存在，更新值并移到头部；若不存在，插入头部。容量超限时删除尾节点，并同步删除哈希表项。

121. 买卖股票的最佳时机

  • 解法：一次遍历。
  • 核心：本质是找“某天卖出 - 之前最低买入价”的最大值。
  • 做法：遍历时维护历史最低价 minPrice，并持续更新 profit = max(profit, price-minPrice)。

1. 两数之和

  • 解法：哈希表。
  • 核心：key 存数字，value 存下标。
  • 注意：一定是先查找目标值是否已出现，再把当前值写入哈希表，避免自己和自己配对。

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

  • 解法：二叉树遍历 + 回溯传递信息。
  • 核心：遍历方向是自顶向下，但题目需要的是“从子树往上汇总结果”，所以关键在递归返回值。
  • 做法：若当前节点是 p 或 q，直接返回；递归左右子树后：
  • 结论 1：若左右都非空，说明 p 和 q 分居两侧，当前节点就是最近公共祖先。
  • 结论 2：若一侧为空，返回另一侧；若都为空，返回空。

53. 最大子序和

  • 解法：动态规划。
  • 定义：dp[i] 表示以 nums[i] 结尾的最大子数组和。
  • 状态转移：dp[i] = max(dp[i-1] + nums[i], nums[i])。
  • 核心：当前位置只有两种选择，要么接在前面的最优连续子数组后面，要么自己重新开一段。
  • 做法：遍历时同步维护全局最大值。

415. 字符串相加

  • 解法：模拟大数加法。
  • 核心：从后往前遍历两个字符串，逐位相加并处理进位。

21. 合并两个有序链表

  • 解法：归并思想。
  • 核心：每次取两个链表当前较小节点接到结果链表后面，时间复杂度 O(n)。

42. 接雨水

  • 解法：单调栈。
  • 核心：寻找“中间低、两边高”的凹槽结构。
  • 做法：维护单调递减栈。当当前柱子高度大于栈顶时，说明形成右边界，可以弹出栈顶作为凹槽底部并结算一次雨水。
  • 计算：设 bottom 为弹出位置，l 为新的栈顶，r 为当前柱子，则本次雨水为 (r - l - 1) * (min(height[l], height[r]) - height[bottom])。

199. 二叉树的右视图

  • 解法：层次遍历。
  • 核心：每层最后一个节点就是右视图中的可见节点。

88. 合并两个有序数组

  • 解法：归并思想。
  • 核心：可以从后往前填充，避免覆盖 nums1 里原本还没处理的数据，时间复杂度 O(n)。

141. 环形链表

  • 解法：快慢指针。
  • 典型扩展：
  • LeetCode 141：判断是否有环。
  • LeetCode 142：寻找链表中环的入口。
  • 进阶：求链表中环的长度。
  • 判断是否有环：fast 和 slow 相遇则说明存在环。
  • 求环长度：在首次相遇点记为 P，继续移动直到再次回到 P，走过的步数就是环长度。
  • 求入口：一个指针从头节点出发，另一个指针从相遇点出发，两者同步前进，再次相遇的位置就是入环点。

33. 搜索旋转排序数组

  • 解法：二分查找。
  • 核心：虽然整体不是完全有序，但二分之后一定有一半是有序的。
  • 做法：先判断 [l, mid] 和 [mid+1, r] 哪一段有序，再根据 target 是否落在有序区间内决定保留哪一半。
  • 常见判断：
  • 若 [l, mid] 有序且 target 在其中，则令 r = mid - 1，否则令 l = mid + 1。
  • 若 [mid+1, r] 有序且 target 在其中，则令 l = mid + 1，否则令 r = mid - 1。

54. 螺旋矩阵

  • 解法：模拟 + 边界收缩。
  • 核心：维护上、下、左、右四条边界，按“左到右、上到下、右到左、下到上”的顺序循环遍历，每走完一条边就收缩对应边界。
  • 注意：边界重合或交错时要及时停止，避免重复访问。

若干实现技巧

  • Python 中可以用 list 模拟队列：s.append(x) 入队，s.pop(0) 出队。
  • Python 中可以用 list 模拟栈：s.append(x) 入栈，s.pop(-1) 出栈。
  • 注意：s.pop(-1) 弹出最后一个元素，s.pop(0) 弹出第一个元素。