LeetCode 180. 连续出现的数字

约 8 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 阿里巴巴
标签
数据库
目录

题目描述

✅ 180. 连续出现的数字

题意分析

Logs 表有 id（主键，自增）与 num 两列。要找出所有至少连续出现三次的数字，输出单列 ConsecutiveNums，同一个数字只输出一次。

这里的「连续」指的是 id 上的连续，即 $id, id+1, id+2$ 三行的 num 相同，而不是「在表里出现三次」。$1, 1, 2, 1$ 这样的数据中 $1$ 出现了三次，但从不连续三行，不应被选出。

题目通常保证 id 从 $1$ 起自增且不含空洞，所以「下一行」可以直接用 id + 1 表达。这一条极其重要——若 id 可能跳号，就必须改用窗口函数 LAG/LEAD 按排序取相邻行，而不能靠算术。

输出要去重：一个数字若连续出现四次，会形成两个长度为三的窗口，不去重会输出两行相同的值。

边界有两处：表中不足三行时结果为空集（这里返回零行是正确的，不像第二高薪水那题要求 null）；同一个数字可能在表中多处各自连续三次，仍只输出一行。

解法：SQL 查询建模

核心思路

用过程式语言解这题很简单：按 id 扫一遍，维护「当前值」与「已连续出现次数」，达到 3 就记入结果集。但 SQL 是集合语言，没有「上一行」这个天然概念，必须把「相邻」显式表达出来。

表达「相邻」有两条路。一条是窗口函数：LAG(num, 1) OVER (ORDER BY id) 与 LAG(num, 2) OVER (ORDER BY id) 取出前两行的值，三者相等即命中。它不依赖 id 连续，是更通用的写法，但需要数据库支持窗口函数（MySQL 8.0+）。

另一条是自连接：把同一张表当作三份 l1、l2、l3，用连接条件 l2.id = l1.id + 1 和 l3.id = l1.id + 2 把它们「错位对齐」，再要求三者的 num 相同。这条路只用最基础的 JOIN，兼容性最好，也是这道经典题最广为流传的解法。本文采用它。

自连接方案的核心是把「一行三值的窗口」重新建模成「三张表的一行连接结果」：连接后的每一行，恰好对应原表中以 l1.id 为起点的一个长度为 3 的窗口，且这个窗口内三个 num 全部相等。连接条件同时承担了两件事——id 的错位（保证相邻）与 num 的相等（保证同值），两者缺一不可。

最后套 DISTINCT 去重：同一个 num 可能对应多个起点（连续 $k$ 次会产生 $k - 2$ 个窗口），也可能在表中不同位置各自连续，去重后每个数字只留一行。

解题步骤

  • 把 Logs 表起三个别名 l1、l2、l3，分别代表窗口的第一、二、三行。起别名是自连接的前提，否则无法区分同一张表的不同副本。
  • 用 l2.id = l1.id + 1 把第二份表向后错一行。这条件把「物理相邻」翻译成了「主键相差 1」，成立的前提正是题目保证的 id 无空洞自增。
  • 在同一个 ON 里加上 l2.num = l1.num。写在 ON 而不是 WHERE 里，语义上更贴切（这是连接成立的条件），执行上也让优化器能更早地裁剪掉不匹配的行；对 INNER JOIN 而言两者结果等价，但对 LEFT JOIN 就完全不同，养成写在 ON 里的习惯更安全。
  • 同理用 l3.id = l1.id + 2 AND l3.num = l1.num 连上第三份表。注意第三份的比较对象仍是 l1.num，而不是 l2.num——虽然此时 l1.num = l2.num 已成立，两种写法等价，但统一以 l1 为基准更不容易写错。
  • SELECT DISTINCT l1.num AS ConsecutiveNums。取 l1.num 是因为三者相等，取哪个都一样；DISTINCT 负责去重；AS 指定的列名必须与题目逐字一致，SQL 判题按列名匹配。

以 Logs = [(1, 1), (2, 1), (3, 1), (4, 2), (5, 1), (6, 2), (7, 2)] 走一遍：

连接过程逐个考察 l1 的候选行。l1.id = 1（num = 1）：需要 id = 2 且 num = 1 的行——存在；需要 id = 3 且 num = 1 的行——存在。这一行连接成功，产出 num = 1。
l1.id = 2（num = 1）：需要 id = 3, num = 1（存在）与 id = 4, num = 1——第 4 行的 num 是 $2$，条件不满足，连接失败。
l1.id = 3（num = 1）：需要 id = 4, num = 1，失败。
l1.id = 4（num = 2）：需要 id = 5, num = 2，而第 5 行是 $1$，失败。
l1.id = 5（num = 1）：需要 id = 6, num = 1，第 6 行是 $2$，失败。
l1.id = 6（num = 2）：需要 id = 7, num = 2（存在）与 id = 8, num = 2——第 8 行不存在，失败。
l1.id = 7：后续两行都不存在，失败。
连接结果只有一行，ConsecutiveNums = 1。DISTINCT 在这里没有起作用，但若把数据改成 [(1,1),(2,1),(3,1),(4,1)]，l1.id = 1 和 l1.id = 2 都会连接成功，各产出一个 $1$，此时 DISTINCT 把两行压成一行——这正是它存在的理由。

代码实现

SELECT DISTINCT l1.num AS ConsecutiveNums
FROM Logs l1
-- id 错位 1 与 2，把「物理相邻的三行」变成「连接后的一行」；
-- num 相等的条件必须同时写进 ON，否则会连出所有相邻三元组。
JOIN Logs l2 ON l2.id = l1.id + 1 AND l2.num = l1.num
JOIN Logs l3 ON l3.id = l1.id + 2 AND l3.num = l1.num;

复杂度分析

  • 时间复杂度：$O(n)$ 到 $O(n \log n)$，$n$ 为 Logs 的行数。id 是主键有索引，两次连接都是等值查找，每行 l1 各做两次 $O(\log n)$ 的索引探查，总计 $O(n \log n)$；若走哈希连接则接近 $O(n)$。最后的 DISTINCT 需要一次去重，代价与结果行数同阶。若 id 上没有索引，自连接会退化成 $O(n^2)$ 的嵌套循环。
  • 空间复杂度：$O(d)$，$d$ 为不同的连续数字个数。连接本身是流式的，不需要物化中间结果；DISTINCT 需要一个哈希表容纳已输出的值，规模不超过结果行数。

关键点总结

  • SQL 没有「上一行」的概念，表达「相邻」只有两条路：主键错位自连接（依赖 id 连续无空洞），或窗口函数 LAG/LEAD（不依赖，更通用）。选哪条要先确认主键的性质，这是这类题的第一个决策点。
  • 自连接的本质是把「一行内看不到的横向关系」转成「多份副本之间的连接条件」。凡是需要比较不同行的题（相邻、同组内两两、自身层级），都可以往这个方向想。
  • 连接条件要尽量写进 ON 而不是 WHERE。对 INNER JOIN 二者等价，但对外连接语义完全不同；统一写在 ON 里既表意清晰又避免日后改成 LEFT JOIN 时出错。
  • 「连续 $k$ 次」会产生 $k - 2$ 个长度为 3 的窗口，所以去重不是可选项。凡是滑动窗口式的匹配，都要检查同一答案会不会被多个窗口重复命中。
  • 面试视角：面试官会先问「如果 id 不连续怎么办」——要能立刻切到 LAG(num,1) OVER (ORDER BY id) 的窗口函数写法；再问「如果要求连续 $N$ 次呢」——自连接需要 $N$ 份副本，不可扩展，正解是用「行号减去按 num 分组的行号」这个经典的分组标记法（ROW_NUMBER() OVER (ORDER BY id) - ROW_NUMBER() OVER (PARTITION BY num ORDER BY id) 在同一段连续中恒定），再按这个标记分组数行数。能主动说出这个技巧，通常直接决定评价。

易错点总结

  • 连接条件漏掉 num 相等：Logs = [(1,1),(2,2),(3,3)] 时任意相邻三行都能连上，会输出 $1$，而没有任何数字连续出现三次，正确结果是空集。
  • 只连一次表（两行判定）：Logs = [(1,1),(2,1),(3,2)] 时 $1$ 只连续两次却被选出，正确结果是空集。
  • 漏写 DISTINCT：Logs = [(1,1),(2,1),(3,1),(4,1)] 会输出两行 $1$，正确结果只有一行。
  • 第三份表的错位写成 l3.id = l2.id + 2：实际错位变成 3，Logs = [(1,1),(2,1),(3,1)] 中需要 id = 4 的行，连接失败输出空集，正确结果是 $1$。
  • 列名写成 num 而非 ConsecutiveNums：判题按列名精确匹配，直接判错。
  • 把 JOIN 写成 LEFT JOIN 且条件全放在 ON 里：Logs = [(1,1),(2,2),(3,3)] 时无匹配的 l2、l3 被补成 null，l1 的每一行都保留下来，SELECT l1.num 会输出 $1, 2, 3$ 三行，正确结果是空集。
  • 误以为「出现三次」就算：Logs = [(1,1),(2,2),(3,1),(4,3),(5,1)] 中 $1$ 出现三次但从不相邻，用 GROUP BY num HAVING COUNT(*) >= 3 会输出 $1$，正确结果是空集。
  • 假设 id 连续但实际有空洞：Logs = [(1,1),(2,1),(5,1)] 中三行的 num 都是 $1$ 却不相邻，id + 1 的写法恰好正确地排除了它；反过来若数据是 [(1,1),(3,1),(5,1)] 而业务上认为它们相邻，自连接会漏判，此时必须改用 LAG。
  • 两个错位方向不一致：写成 l2.id = l1.id + 1 配 l3.id = l1.id - 1，连的其实是「前一行和后一行」，窗口以 l1 为中心而非起点；Logs = [(1,1),(2,1),(3,1),(4,1)] 会命中 l1.id 为 2 和 3 两个中心，与按起点计数的窗口数不同，一旦后续要统计窗口数量就会算错。
  • l3 只与 l2 比 num 而不与 l1 关联，同时 l2 也漏了与 l1 的比较：Logs = [(1,1),(2,2),(3,2)] 中 l2、l3 的 num 相等而 l1 不同，连接成立并输出 l1.num = 1，正确结果是空集。

相似题目

题目 难度 考察点
197. 上升的温度 简单 同为相邻行比较，但错位依据是日期而非主键，需用日期函数而非加一
181. 超过经理收入的员工 简单 自连接的另一形态，连接依据是外键指向本表，比较的是同一行的两个角色
182. 查找重复的电子邮箱 简单 只关心出现次数不关心是否相邻，用 GROUP BY 加 HAVING 即可
178. 分数排名 中等 需要跨行的名次信息，窗口函数 DENSE_RANK() 是标准解
176. 第二高的薪水 中等 同样要在有序集合上定位特定位置，靠 LIMIT/OFFSET 而非行间连接
184. 部门工资最高的员工 中等 分组内取极值，需关联子查询或 PARTITION BY，比较发生在组内而非相邻行
185. 部门工资前三高的所有员工 困难 分组内取前三个不同值，DENSE_RANK() 的典型场景，自连接写法会指数膨胀
196. 删除重复的电子邮箱 简单 同为自连接定位目标行，但执行的是 DELETE，要处理 MySQL 的同表限制