LeetCode 180. 连续出现的数字
题目描述
题意分析
找出至少连续出现三次的数字，每个数字只返回一次。下面的查询按连续编号检查相邻记录，即
id、id+1、id+2这三条记录的num必须相同。
解法：SQL 查询建模
核心思路
[!blue]
至少连续出现三次，等价于存在一个连续三条记录都相同的窗口：更长的连续段一定包含这样的三条，不必枚举整段长度。因此把同一张
Logs表取三个别名l1、l2、l3，分别代表窗口内的三条记录。以
l1为起点，要求l2.id = l1.id+1、l3.id = l1.id+2，并且两条后续记录的num都等于l1.num。编号条件限制连续位置，数值条件限制内容相同；内连接只有在两条后续记录都匹配时才留下这一窗口。长度超过三的连续段会产生多个重叠窗口，同一个数字也可能在不同位置形成连续段，所以最终用
DISTINCT只输出一次num。没有匹配窗口时返回空结果。查询通过明确的编号差判断连续性，不依赖表的物理存储顺序。
解题步骤
- 以第一份表为窗口起点。
- 连接编号加一且同值的第二行。
- 连接编号加二且同值的第三行。
- 对结果数字去重。
代码实现
-- 连续长段产生重叠窗口，同一个数字最终只输出一次
SELECT DISTINCT l1.num AS ConsecutiveNums
FROM Logs l1
-- 第二条记录编号加一，同时要求数字相同
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;
复杂度分析
- 时间复杂度：
n为日志行数，每条起始记录需查找另外两条记录；按主键索引查找通常可按 $O(n\log(n+1))$ 估算，连接与去重的实际成本取决于执行计划。- 空间复杂度：取决于连接和去重方式，哈希计划可用 $O(n)$ 辅助空间，不能统一假定连接无需额外存储。
关键点总结
[!green]
- 编号错位保证相邻，值相等保证连续重复，两类条件都需要。
- 同一数字可以由多个窗口命中，所以结果去重。
易错点总结
[!yellow]
- 只按数字分组计数三次，无法保证连续。
- 第三行按第二行再加二，会错误检查间隔三的位置。
- 使用左连接却直接输出第一行，会把没有三行匹配的值也输出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 601. 体育馆的人流量 | 困难 | 同样识别连续记录形成的段，原题还要求段内人数满足阈值，本题要求数字相同。 |
| 197. 上升的温度 | 简单 | 同样比较相邻记录关系，但原题按相邻日期，本题按日志记录次序，不能混用连接条件。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！