江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第180题：连续出现的数字

表：Logs +-------------+---------+ | Column Name | Type | +-------------+---------+ | id | int | | num | varchar | +-------------+---------+ id 是这个表的主键。 编写一个 SQL 查询，查找所有至少连续出现三次的数字。

题目描述

表：Logs

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| num         | varchar |
+-------------+---------+
id 是这个表的主键。

编写一个 SQL 查询，查找所有至少连续出现三次的数字。

返回的结果表中的数据可以按 任意顺序 排列。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1:

输入：
Logs 表：
+----+-----+
| id | num |
+----+-----+
| 1  | 1   |
| 2  | 1   |
| 3  | 1   |
| 4  | 2   |
| 5  | 1   |
| 6  | 2   |
| 7  | 2   |
+----+-----+
输出：
+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+
解释：1 是唯一连续出现至少三次的数字。

提示

  • id 是这个表的主键。
  • 表中存在重复的数字。
  • 连续出现的定义是 id 连续。

解题思路

方法一：使用自连接（Self Join）

我们可以使用自连接来查找连续出现的数字。基本思路是：

关键点：

  1. 将表与自身连接三次，找出连续的三个 id
  2. 确保这三个 id 对应的 num 值都相同
  3. 去重以获得唯一的连续数字列表

时间复杂度：O(n²)，其中 n 是 Logs 表中的行数（自连接的时间复杂度） 空间复杂度：O(n)

方法二：使用窗口函数（Window Function）

在支持窗口函数的数据库中，我们可以使用 LAG 和 LEAD 函数来找出连续出现的数字。

关键点：

  1. 使用 LAG 获取前一行的值
  2. 使用 LEAD 获取后一行的值
  3. 比较当前行、前一行和后一行的值是否相等

时间复杂度：O(n log n)，其中 n 是 Logs 表中的行数（排序的时间复杂度） 空间复杂度：O(n)

方法三：使用用户变量（仅适用于 MySQL）

在 MySQL 中，我们可以使用用户变量来跟踪连续的数字。

关键点：

  1. 使用用户变量跟踪前一个数字和连续出现的次数
  2. 当当前数字与前一个数字相同时，增加计数
  3. 当当前数字与前一个数字不同时，重置计数

时间复杂度：O(n)，其中 n 是 Logs 表中的行数 空间复杂度：O(n)

代码实现

SQL 实现（方法一：自连接）

SELECT DISTINCT l1.num AS ConsecutiveNums
FROM Logs l1, Logs l2, Logs l3
WHERE l1.id = l2.id - 1 
  AND l2.id = l3.id - 1
  AND l1.num = l2.num 
  AND l2.num = l3.num;

SQL 实现（方法二：窗口函数）

SELECT DISTINCT num AS ConsecutiveNums
FROM (
    SELECT num,
           LAG(num) OVER (ORDER BY id) AS prev_num,
           LEAD(num) OVER (ORDER BY id) AS next_num
    FROM Logs
) t
WHERE num = prev_num AND num = next_num;

SQL 实现（方法三：使用用户变量）

SELECT DISTINCT num AS ConsecutiveNums
FROM (
    SELECT num,
           @count := IF(@prev = num, @count + 1, 1) AS cnt,
           @prev := num
    FROM Logs, (SELECT @prev := NULL, @count := 0) AS init
    ORDER BY id
) AS t
WHERE cnt >= 3;

性能分析

各SQL实现的性能对比：

实现方法 执行用时 内存消耗 特点
方法一 379 ms 0B 简单直观，但性能较差
方法二 342 ms 0B 较简洁，性能适中
方法三 324 ms 0B 性能最佳，但仅适用于MySQL

补充说明

代码亮点

  1. 方法一使用自连接，思路简单直观，容易理解
  2. 方法二使用窗口函数，代码简洁，可读性好
  3. 方法三使用用户变量，在查询效率上有优势

方法比较

  • 方法一：最简单直接的实现，但当表很大时可能会有性能问题
  • 方法二：使用现代 SQL 特性，代码简洁，可读性好
  • 方法三：性能最好，但使用了 MySQL 特有的用户变量，可移植性较差

常见错误

  1. 忘记使用 DISTINCT 去除重复结果
  2. 在方法一中，连接条件写错，导致不是查找连续的 id
  3. 在方法三中，用户变量的初始化或更新逻辑错误
  4. 没有正确理解“连续”的定义（根据题目，是基于 id 的连续，而不是基于表中的位置）

相关题目