时间复杂度

看增长趋势，不看机器速度

复杂度描述输入规模变大后，算法执行次数如何增长。写题时先数循环层数，再观察有没有二分、排序、递归分治或剪枝。

  • O(1)：常数操作，例如访问数组下标。
  • O(log n)：每次把范围缩小一半，例如二分查找。
  • O(n)：每个元素看一次，例如遍历数组。
  • O(n log n)：常见于排序、分治。
  • O(n²)：两层循环枚举 pair。
空间复杂度

额外开了多少内存

空间复杂度不只看输入数组本身，更关注你为了计算额外创建了多少结构。哈希表、辅助数组、递归栈、动态规划表都要算。

  • 原地交换通常是 O(1)。
  • 哈希表记录出现次数通常是 O(n)。
  • 递归深度为 n 时，调用栈也是 O(n)。
  • 二维 DP 表一般是 O(nm)，可尝试滚动数组优化。
边界条件

最容易丢分的地方

很多代码不是思路错，而是边界没覆盖。提交前至少手动测空输入、单元素、重复值、负数、最大值、找不到目标、刚好在开头或结尾。

  • 循环条件是 `<` 还是 `<=`。
  • 下标是否会访问到 `-1` 或 `n`。
  • 答案初始值是否合理。
  • 返回空数组、-1、0 还是 false。

常见题型识别表

题目特征优先考虑判断理由
有序数组、查找位置、最小可行值二分查找有单调性，可以不断缩小答案范围。
连续子数组、最长/最短、和或字符频次滑动窗口窗口左右边界移动，每个元素进出窗口一次。
两数之和、去重、出现次数哈希表用空间换时间，把查找从 O(n) 降到接近 O(1)。
括号匹配、最近未匹配、撤销操作栈后进先出，天然适合处理最近状态。
层序遍历、最短步数、扩散过程队列/BFS按层推进，第一次到达通常就是最短。
所有方案、排列组合、路径选择回溯需要试探、撤销、继续尝试下一种选择。
最优值、重复子问题、当前依赖过去动态规划定义状态，写转移方程，按依赖顺序计算。

数组和字符串

核心能力

  • 会遍历，知道下标从 0 到 n-1。
  • 会维护最大值、最小值、计数、前一个元素。
  • 会用辅助数组记录前缀和、差分、标记。
  • 字符串题常把字符当数组处理。

常见题目

  • 反转字符串、旋转数组。
  • 寻找最大连续和。
  • 合并两个有序数组。
  • 统计字符出现次数。

易错点

  • 循环边界多一位或少一位。
  • 原地修改时覆盖了还没用的数据。
  • 字符串比较大小和数字比较混用。
  • 空字符串、空数组没有单独处理。

哈希表

哈希表适合快速判断“有没有出现过”“出现了几次”“某个值对应什么”。它的典型写法是边遍历边记录，或者先统计再查询。

  • 两数之和：遍历 x 时查 target - x 是否出现。
  • 字符异位词：统计每个字符频次。
  • 去重：用 Set 保存已经访问过的值。
  • 映射关系：用 Map 保存 key 到 value。

前缀和

前缀和用来快速求区间和。`prefix[i]` 表示前 i 个数的和，区间 `[l,r]` 的和等于 `prefix[r+1] - prefix[l]`。

一维前缀和：`prefix[i+1] = prefix[i] + arr[i]`
区间和：`sum(l,r) = prefix[r+1] - prefix[l]`
连续子数组和为 k：记录前缀和出现次数。

双指针

双指针的本质是用两个位置共同表示当前状态。常见有左右夹逼、快慢指针、读写指针三类。

  • 左右夹逼：有序数组两数之和。
  • 快慢指针：链表判环、删除倒数第 k 个节点。
  • 读写指针：原地删除重复元素。

滑动窗口

滑动窗口适合连续区间问题。右指针扩张窗口，左指针在条件不满足时收缩窗口，窗口内维护频次、和、最大值等信息。

  • 最长无重复子串。
  • 长度最小的子数组。
  • 包含全部目标字符的最短子串。
  • 固定长度窗口最大平均值。

二分查找

二分不只用于“找某个数”，还常用于“找第一个满足条件的位置”或“答案最小是多少”。关键是判断条件必须具有单调性。

三问法

  • 搜索区间是什么。
  • mid 满足条件时，答案在左边还是右边。
  • 最后返回 left、right 还是 mid。

常见变形

  • 找目标值下标。
  • 找第一个大于等于 target 的位置。
  • 找最后一个小于等于 target 的位置。
  • 在答案范围上二分。

栈

栈是后进先出。只要题目里出现“最近的一个”“匹配”“撤销”“单调关系”，就可以想栈。

  • 括号匹配：左括号入栈，右括号匹配栈顶。
  • 单调栈：维护递增或递减，求下一个更大元素。
  • 表达式求值：数字栈和符号栈。

队列

队列是先进先出。BFS、层序遍历、任务调度、缓存淘汰都常用队列。

  • 树的层序遍历：每次处理一层。
  • 图的最短路径：边权相同可以 BFS。
  • 滑动窗口最大值：用单调队列维护候选最大值。

排序

排序复杂度适用场景注意点
冒泡排序O(n²)教学、理解交换大数据会超时。
选择排序O(n²)简单实现每轮找最小值放前面。
插入排序O(n²)数据基本有序小规模时很实用。
归并排序O(n log n)稳定排序、逆序对需要辅助数组。
快速排序平均 O(n log n)通用排序极端情况下可能退化。
堆排序O(n log n)Top K、优先队列理解堆顶含义。

递归

递归就是函数调用自己。写递归时不要试图在脑中展开所有层，先明确函数含义，再写终止条件和递推关系。

  • 函数定义：这个函数返回什么。
  • 终止条件：什么时候不再递归。
  • 递归拆分：问题如何变小。
  • 合并结果：子问题答案如何组成总答案。

回溯

回溯用于枚举所有方案。基本动作是选择、递归、撤销选择。组合、排列、子集、棋盘路径都属于典型题。

  • 用 path 保存当前方案。
  • 用 start 控制组合不重复。
  • 用 used 控制排列不重复。
  • 剪枝可以减少无意义搜索。

动态规划

动态规划适合有重复子问题和最优子结构的题。不要一上来写代码，先把状态、转移、初始化、遍历顺序讲清楚。

五步法

  • 定义状态：`dp[i]` 表示什么。
  • 写转移：从哪些旧状态得到新状态。
  • 初始化：最小规模的答案。
  • 遍历顺序：保证依赖先被算出来。
  • 返回答案：最后取哪个状态。

常见模型

  • 斐波那契：当前依赖前两个。
  • 背包：容量和物品选择。
  • 最长递增子序列：以 i 结尾的最优值。
  • 路径 DP：从上或左转移到当前格。

常见坑

  • 状态定义模糊，导致转移写不出来。
  • 初始化漏了 0 或 1 的情况。
  • 背包遍历方向写反。
  • 把子串和子序列混淆。

贪心

贪心每一步选择当前看起来最优的方案。它需要证明局部最优可以推出全局最优，否则很容易错。

  • 区间调度：按结束时间排序。
  • 跳跃游戏：维护当前能到的最远位置。
  • 分发饼干：小饼干优先满足小胃口。
  • 买卖股票：能赚就累加差价。

堆和优先队列

堆适合动态维护最大值或最小值。Top K、合并有序链表、任务调度、数据流中位数都常用堆。

  • 最小堆：堆顶是最小元素。
  • 最大堆：堆顶是最大元素。
  • Top K 大：维护大小为 K 的最小堆。
  • Top K 小：维护大小为 K 的最大堆。

二叉树

树题重点是遍历。前序适合复制树、序列化；中序适合二叉搜索树；后序适合自底向上计算高度、直径、平衡性。

  • 前序：根、左、右。
  • 中序：左、根、右。
  • 后序：左、右、根。
  • 层序：用队列一层层遍历。

二叉搜索树

BST 的特点是左子树小于根，右子树大于根。中序遍历会得到有序序列。

  • 查找、插入可以按大小走左或右。
  • 验证 BST 可用上下界。
  • 第 k 小元素可中序计数。
  • 最近公共祖先可利用大小关系。

图论基础

图由点和边组成。写图题第一步是建图，第二步是选择遍历方式。无权最短路常用 BFS，有权最短路常用 Dijkstra。

  • 邻接表适合稀疏图。
  • 邻接矩阵适合点少、查边快。
  • DFS 适合连通块、路径搜索。
  • BFS 适合最短步数、层级扩散。

并查集

并查集用于维护集合合并关系。常见于连通块、朋友圈、岛屿合并、判断是否成环。

  • find：找到当前节点所在集合代表。
  • union：把两个集合合并。
  • 路径压缩：让 find 更快。
  • 按秩合并：减少树高度。

二分查找模板

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

滑动窗口模板

function windowTemplate(arr) {
  let left = 0;
  let answer = 0;
  const count = new Map();

  for (let right = 0; right < arr.length; right++) {
    const x = arr[right];
    count.set(x, (count.get(x) || 0) + 1);

    while (/* 窗口不合法 */ false) {
      const y = arr[left];
      count.set(y, count.get(y) - 1);
      left++;
    }

    answer = Math.max(answer, right - left + 1);
  }
  return answer;
}

回溯模板

function backtrackTemplate(nums) {
  const ans = [];
  const path = [];

  function dfs(start) {
    ans.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(0);
  return ans;
}

动态规划模板

function fib(n) {
  if (n < 2) return n;
  let prev = 0;
  let curr = 1;
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

BFS 模板

function bfs(start, graph) {
  const queue = [start];
  const visited = new Set([start]);

  while (queue.length) {
    const node = queue.shift();
    for (const next of graph[node] || []) {
      if (visited.has(next)) continue;
      visited.add(next);
      queue.push(next);
    }
  }
  return visited.size;
}

提交评测排错清单

输出格式

  • 不要输出“答案是”之类提示文字。
  • 多个数字按题目要求用空格、换行或逗号分隔。
  • 字符串答案注意大小写。
  • 布尔值注意是 true/false 还是 1/0。

语言差异

  • JavaScript 按题目函数名返回结果。
  • C/C++/Java/Python 从标准输入读取，输出答案。
  • Java 类名固定使用 Main。
  • C/C++ 不要依赖本地文件输入。

测试习惯

  • 先跑样例，再跑边界。
  • 自己构造反例，不要只看一组数据。
  • 如果 0%，优先看失败原因。
  • 如果超时，检查是否有死循环或 O(n²) 过大。