详解力扣高频SQL50题之180. 连续出现的数字【困难】

传送门：180. 连续出现的数字

题目

表：Logs

±------------±--------+
| Column Name | Type |
±------------±--------+
| id | int |
| num | varchar |
±------------±--------+
在 SQL 中，id 是该表的主键。
id 是一个自增列。

找出所有至少连续出现三次的数字。

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

结果格式如下面的例子所示：

示例 1:

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

方法一：row_number()

解析

官方题解是死代码，只能应对连续三次，他们自己都不知道最佳解法，所以本人认为这题可以定级为困难。
判断元素连续出现次数其实有个经典的公式：全局行号-它的分组排序行号（分组排名），每组中差值相同个数即其连续出现次数，而分组，排序并赋予排名是row_number()的特性，而全局行号数组是有序数组，为方便，这里默认全局行号和row_number()都是按递增排序的，所以全局行号即表中的id，分组排名即row_number()后的值，全局行号-分组排名中相同数字个数即对应的数字连续出现个数，结果如下表所示：

有了这个表格后，计算过程就很明显了，先求出id-row_number()按num分组的排名，别名rn，再嵌套一层查询求组内相同rn的个数>=3的记录，组内相同rn的数量，即按num和rn分组后的组内数量，所以要按num和rn分组，再筛选组内数量>=3的记录，坑点来了：按num和rn分组不意味着num是唯一的，只有按num分组才能保证num唯一，所以必须对num去重后再返回num。

代码（标准SQL）

select distinct num as ConsecutiveNums
from(select num,
id-row_number()over(partition by num order by id) as rn
from Logs)
group by num,rn
having count(*)>=3;

方法二：lead()

解析

学过开窗函数的都知道，lead()是把当前行的后面几行往上拉，lag()则相反，这题用lag()或lead()都行，本人习惯用lead()，所以这里仅介绍lead()解法。lead()解法和row_number()解法类似，也是求差值，但更简单，因为原理是：若全局行号-它的分组后n行号=-n，则分组字段至少出现n+1次。和上个方法一样，全局行号数组必须是有序数组，即id，id后2行用lead(id,2)实现，需要升序排序，结果如下表所示：

有了这个表格后，计算过程就很明显了，先对id求lead()，按num分组，按id升序，再减去id，别名rn，再嵌套一层查询，求组内rn=2的记录，即出现3次的num，但它不止一个，所以仍要对num去重后再返回num。

代码（标准SQL）

select distinct num as ConsecutiveNums
from(select num,
id-lead(id,2)over(partition by num order by id) as rn
from Logs)
where rn=-2;

总结下两个方法：
假设存在一个有序的全局行号数组和一个分组字段，求至少连续出现n次的分组字段，有两种方法：
1.全局行号-它的分组排名，每组中差值相同个数即分组字段连续出现次数，其中分组排名用row_number()实现，需要排序。
2.若全局行号-它的分组后n行号=-n，则分组字段至少出现n+1次，其中分组后n行号用lead(全局行号,n)实现，需要排序。
注意：全局行号还包括日期。