LeetCode Hot 100 算法总结

LeetCode Hot 100 确实是面试中出现频率最高的题目，它们覆盖了解决算法问题最核心、最经典的思想。虽然题目看似千变万化，但其背后考察的算法和数据结构模式是高度集中的。

与其将这100道题看作是独立的个体，不如将它们视为对几个核心算法思想的反复练习和变种应用。掌握了这些通用模式，不仅可以解决 Hot 100，更能举一反三，应对各种面试题。

以下是我为你总结的，可以用以“通杀” LeetCode Hot 100 的几个核心算法模式，并以 JavaScript 语言为例进行说明。

核心算法模式总结

可以将 Hot 100 的题目大致归为以下几个核心类别。掌握了它们，你就掌握了通关的钥匙。

1. 双指针 (Two Pointers)

双指针是一种极其高效的技巧，通过维护两个指针在数组或链表中的移动，来解决问题。它能巧妙地将一些 O(N2) 的暴力解法优化到 O(N)。

• 核心思想: 用两个指针（通常命名为 left 和 right，或 slow 和 fast）从不同位置（同向、反向或分离）开始，根据特定条件移动它们，直到它们相遇或交错，从而完成任务。

• 常见模式:

  • 快慢指针: 主要用于解决链表问题，如判断环、寻找中点、寻找倒数第K个节点。一个指针每次走一步（slow），另一个指针每次走两步（fast）。

  • 左右指针: 主要用于有序数组，通过从两端向中间逼近来寻找目标和或满足条件的区间。

  • 滑动窗口: 见下一个类别，它是双指针思想的一种特例和延伸。

• 典型例题:

  • 11. 盛最多水的容器: 典型的左右指针，从两端开始，每次移动指向较短板子的指针。

  • 142. 环形链表 II: 快慢指针的经典应用，通过数学推导确定环的入口。

  • 283. 移动零: 快慢指针（或同向双指针），一个指针（slow）指向新数组的末尾，另一个指针（fast）遍历原数组。

• JavaScript 通用模板 (左右指针):

  JavaScript

  function twoPointers(arr) {
      let left = 0;
      let right = arr.length - 1;
      let result;
  
      while (left < right) {
          // 根据 arr[left] 和 arr[right] 的关系进行逻辑判断
          if (condition(arr[left], arr[right])) {
              // 移动其中一个指针
              left++;
          } else {
              right--;
          }
      }
      return result;
  }
  

2. 滑动窗口 (Sliding Window)

滑动窗口是双指针思想的集大成者，专门用于解决数组或字符串中的“连续子数组”或“连续子串”问题，如寻找最长的、最短的、满足特定条件的子数组/子串。

• 核心思想: 维护一个由 left 和 right 指针界定的“窗口”。right 指针负责扩大窗口，纳入新元素；left 指针负责在窗口不满足条件时收缩窗口，排除旧元素。整个过程 left 和 right 都只向右移动，保证了 O(N) 的时间复杂度。

• 典型例题:

  • 3. 无重复字符的最长子串: 窗口内维持没有重复的字符。

  • 76. 最小覆盖子串: 窗口需要覆盖目标字符串 t 中的所有字符。

  • 438. 找到字符串中所有字母异位词: 维持一个固定大小的窗口，判断窗口内的字符计数是否与目标一致。

• JavaScript 通用模板:

  JavaScript

  function slidingWindow(s, t) {
      const window = new Map(); // 或者使用对象 {}
      const need = new Map(); // 存储目标字符和其数量
      for (const char of t) {
          need.set(char, (need.get(char) || 0) + 1);
      }
  
      let left = 0, right = 0;
      let valid = 0; // 记录窗口中满足条件的字符种类数
  
      while (right < s.length) {
          // c 是将移入窗口的字符
          const c = s[right];
          right++; // 扩大窗口
  
          // 进行窗口内数据的一系列更新
          if (need.has(c)) {
              window.set(c, (window.get(c) || 0) + 1);
              if (window.get(c) === need.get(c)) {
                  valid++;
              }
          }
  
          // 判断左侧窗口是否要收缩
          while (/* window needs shrink */ valid === need.size) {
              // 在这里更新最终结果
              // ...
  
              // d 是将移出窗口的字符
              const d = s[left];
              left++; // 收缩窗口
  
              // 进行窗口内数据的一系列更新
              if (need.has(d)) {
                  if (window.get(d) === need.get(d)) {
                      valid--;
                  }
                  window.set(d, window.get(d) - 1);
              }
          }
      }
      return result;
  }
  

3. 树的遍历 (Tree Traversal)

二叉树问题在 Hot 100 中占据了相当大的比重。其核心解法万变不离其宗，都基于深度优先搜索（DFS）和广度优先搜索（BFS）。

• 核心思想:

  • DFS (深度优先搜索): 深入到树的某一分支的尽头，再回溯。通常用递归或栈实现。前序、中序、后序遍历是其基础。

  • BFS (广度优先搜索): 从根节点开始，一层一层地向外扩展。通常用队列实现。

• 解题思路: 绝大多数树的问题，都可以思考：

  1. 我对于当前这个节点 root，需要做什么？

  2. 我需要从我的左、右子树拿到什么信息，才能完成 root 节点的工作？

  3. 我应该向上返回什么信息，以供我的父节点使用？

     这个思考过程，本质上就是定义递归函数的签名和返回值。

• 典型例题:

  • 94. 二叉树的中序遍历: DFS 的基础，递归或迭代（用栈）实现。

  • 102. 二叉树的层序遍历: BFS 的直接应用。

  • 104. 二叉树的最大深度: DFS 的经典应用，maxDepth(root) = 1 + max(maxDepth(root.left), maxDepth(root.right))。

  • 226. 翻转二叉树: DFS，交换左右子树，然后递归翻转。

  • 543. 二叉树的直径: DFS 的变种，对于每个节点，其直径为 左子树深度 + 右子树深度，需要全局维护最大值。

• JavaScript 通用模板 (DFS 递归):

  JavaScript

  /**
   * Definition for a binary tree node.
   * function TreeNode(val, left, right) {
   * this.val = (val===undefined ? 0 : val)
   * this.left = (left===undefined ? null : left)
   * this.right = (right===undefined ? null : right)
   * }
   */
  function dfs(root) {
      if (!root) {
          return /* base case 的返回值 */;
      }
  
      // 递归获取左右子树的结果
      const leftResult = dfs(root.left);
      const rightResult = dfs(root.right);
  
      // 利用左右子树的结果，结合当前节点的值，计算当前节点的结果
      // ...
  
      return /* 返回给父节点的结果 */;
  }
  

4. 动态规划 (Dynamic Programming, DP)

动态规划是 Hot 100 中的重中之重，也是很多人觉得困难的部分。但其本质有章可循。

• 核心思想: 将一个大问题分解为相互重叠的子问题，通过求解子问题来得到大问题的解。为了避免重复计算，会用一个 DP 表（通常是一维或二维数组）来存储子问题的解。

• 解题五步曲:

  1. 定义 dp 数组的含义: 这是最关键的一步。例如，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

  2. 找出状态转移方程: 思考 dp[i] 如何由之前的 dp[j] (其中 j < i) 推导出来。这是核心。

  3. 确定 dp 数组的初始化: dp[0] 的值是什么？或者整个数组的初始值是什么？

  4. 确定遍历顺序: 是从前到后，还是从后到前？

  5. 确定最终返回值: 最终结果是 dp[n-1] 还是 max(dp)？

• 典型例题:

  • 53. 最大子数组和: dp[i] 定义为以 nums[i] 结尾的最大子数组和。状态转移：dp[i] = max(nums[i], nums[i] + dp[i-1])。

  • 300. 最长递增子序列: dp[i] 定义为以 nums[i] 结尾的最长递增子序列的长度。

  • 70. 爬楼梯: dp[i] 定义为爬到第 i 阶的方法数。状态转移：dp[i] = dp[i-1] + dp[i-2]。

  • 5. 最长回文子串: dp[i][j] 定义为字符串 s 从索引 i 到 j 的子串是否是回文串。

• JavaScript 通用模板 (一维 DP):

  JavaScript

  function dynamicProgramming(input) {
      const n = input.length;
      // 1. 定义 dp 数组
      const dp = new Array(n).fill(initial_value);
  
      // 3. 初始化
      dp[0] = /* ... */;
  
      // 4. 遍历
      for (let i = 1; i < n; i++) {
          // 2. 状态转移方程
          // 通常会再嵌套一个循环来寻找之前的状态
          for (let j = 0; j < i; j++) {
              dp[i] = /* 根据 dp[j] 和 input[i] 计算 */;
          }
      }
  
      // 5. 返回值
      return /* dp[n-1] 或 Math.max(...dp) */;
  }
  

5. 回溯算法 (Backtracking)

回溯法是暴力搜索的优化，可以看作是“有纪律的”暴力枚举。它在 DFS 的框架上，增加了“状态重置”（也叫“剪枝”）的操作。非常适合解决组合、排列、子集、棋盘等问题。

• 核心思想: 像在一棵“解空间树”上进行 DFS。从根节点出发，尝试一个选择，进入下一层决策；如果发现这个选择走不通（或已经走到头），就撤销这个选择（回溯），尝试同一层的其他选择。

• 解题框架:

  1. 函数签名: backtrack(路径, 选择列表)

  2. 结束条件: 满足什么条件时，将“路径”加入结果集，并返回。

  3. 循环和选择: 遍历当前可用的“选择列表”。

  4. 做选择: 将当前选择加入“路径”。

  5. 递归: backtrack(新路径, 新选择列表)。

  6. 撤销选择: 将刚才加入“路径”的选择移除，恢复现场，以便进行下一次循环尝试。

• 典型例题:

  • 46. 全排列: 数字不能重复使用。

  • 78. 子集: 经典的求所有子集问题。

  • 22. 括号生成: 通过控制左右括号的数量进行剪枝。

  • 39. 组合总和: 数字可以重复使用。

• JavaScript 通用模板:

  JavaScript

  function backtracking(nums) {
      const result = [];
      const path = []; // 记录当前路径
  
      function backtrack(startIndex) { // startIndex 用于去重和避免重复组合
          // 收集结果，注意需要拷贝 path
          // result.push([...path]); // 如果是求子集，在这里收集
  
          // 终止条件
          if (path.length === /* 目标长度 or 其他条件 */) {
              result.push([...path]);
              return;
          }
  
          for (let i = startIndex; i < nums.length; i++) {
              // 做选择
              path.push(nums[i]);
              // 递归
              backtrack(i + 1); // i+1 表示数字不可重复使用
              // 撤销选择
              path.pop();
          }
      }
  
      backtrack(0);
      return result;
  }
  

学习路径建议

我认为最高效的学习路径是：

1. 数组/链表基础 -> 双指针/滑动窗口: 这是最基础且效果最立竿见影的。先从数组和链表的基本操作开始，然后迅速切入双指针和滑动窗口，解决 Hot 100 中近 20% 的题目。

2. 哈希表 (Map/Set): 哈希表是优化时间复杂度的神器，是几乎所有算法模式的“润滑剂”。例如，在滑动窗口中记录字符数，在两数之和中寻找目标值。务必熟练使用 Map 和 Set。

3. 树 -> DFS/BFS: 掌握树的两种遍历方式，并理解递归的本质。练习 Hot 100 中所有树的题目，你会发现它们的解法高度统一。

4. 回溯算法: 在理解了 DFS 的基础上学习回溯，你会发现它就是 DFS 的一个标准框架。专门练习组合、排列、子集问题。

5. 动态规划: 这是攻坚阶段。不要急于求成，从最简单的爬楼梯、最大子数组和开始，真正理解“五步曲”，然后逐步挑战更复杂的二维 DP 和背包问题。

我的最终建议是：不要孤立地刷题，而要带着“模式识别”的眼光去刷。

每当你看到一道题，先不要急着写代码，而是问自己：

• 这道题的输入和输出是什么？

• 它看起来像我学过的哪种模式？是求连续子数组问题吗（滑动窗口）？是求最优解吗（动态规划）？是求所有可能性吗（回溯）？

• 如果套用这个模式的通用模板，我需要修改哪些部分？

当你能够为 Hot 100 中的每一道题清晰地打上“双指针”、“DP”、“回溯”等标签，并能复述出其核心思想和代码框架时，你就真正掌握了它们，也具备了快速学习和解决新问题的能力。