SQL实战：02之连续数问题求解

概述

最近刷题时遇到了一些有意思的题，查询连续出现多次的数或者最长的连续序列，而且出现了多次，对于这种题的实现思想就是利用等差数列的思想来解决。

一个连续的序列减一个连续的序列的差值一定是相同的。

例如有一个整数序列A:

[4,5,6,7,8,10,11,12,15,19] 

可以看到其中有些数据是连续的，有些不是连续的。为了找出这些 连续的序列可以按照从小到大给这组数排序，得到一个排名序列B，如下： 
[1,2,3,4,5,6,7,8,9,10]

利用序列A - 序列B

得到的答案是[3,3,3,3,3,4,4,4,6,9]

可以很明显的看出只要是连续的值得到的差值都是相同的。

利用这个思想，就可以很方便的解决这类问题。

题目:体育馆的人流量

表：Stadium
+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| visit_date    | date    |
| people        | int     |
+---------------+---------+
visit_date 是该表中具有唯一值的列。
每日人流量信息被记录在这三列信息中：序号 (id)、日期 (visit_date)、 人流量 (people)
每天只有一行记录，日期随着 id 的增加而增加
 

编写解决方案找出每行的人数大于或等于 100 且 id 连续的三行或更多行记录。

返回按 visit_date 升序排列 的结果表。

查询结果格式如下所示。

 

示例 1:

输入：
Stadium 表:
+------+------------+-----------+
| id   | visit_date | people    |
+------+------------+-----------+
| 1    | 2017-01-01 | 10        |
| 2    | 2017-01-02 | 109       |
| 3    | 2017-01-03 | 150       |
| 4    | 2017-01-04 | 99        |
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-09 | 188       |
+------+------------+-----------+
输出：
+------+------------+-----------+
| id   | visit_date | people    |
+------+------------+-----------+
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-09 | 188       |
+------+------------+-----------+
解释：
id 为 5、6、7、8 的四行 id 连续，并且每行都有 >= 100 的人数记录。
请注意，即使第 7 行和第 8 行的 visit_date 不是连续的，输出也应当包含第 8 行，因为我们只需要考虑 id 连续的记录。
不输出 id 为 2 和 3 的行，因为至少需要三条 id 连续的记录。

题解

因为要求解id连续的三行或者更多行的记录，且每行人数大于或等于100，这个就是典型的 求解 连续序列的问题。对于这类问题的核心思想就是利用等差数列来求解，一个连续递增的序列减另一个连续递增的序列，得到的差值是相同的。

步骤一：构造出一个连续序列

利用row_number() 函数，按照id的升序排列构造出一个连续的序列（1，2，3，4，5等等）并且过滤出人数大于等于100的行。再使用id减去row_number，会得到一个值

with grouped_table AS(
    SELECT id
            ,id - row_number() over(order by id ASC) AS groupID
            ,visit_date
            ,people
    FROM Stadium where people >= 100
)

步骤二：找出符合条件的组的序号

第一步ID减去row_number后，如果id是连续的，那么得到的差值group_id一定是相等的，所以可以通过groupID来做分组查询，统计出连续序列的长度，并过滤出连续的三行或者更多行的groupID。

hinted_group_table As(
    SELECT  groupID from grouped_table group by groupID having count(*) >= 3
)

步骤三：fetch结果，使用内连接过滤出符合条件的记录。

SELECT id,visit_date,people FROM grouped_table T1,hinted_group_table T2 where T1.groupID = T2.groupID;

完整SQL

with grouped_table AS(
    SELECT id
            ,id - row_number() over(order by id ASC) AS groupID
            ,visit_date
            ,people
    FROM Stadium where people >= 100
),

hinted_group_table As(
    SELECT  groupID from grouped_table group by groupID having count(*) >= 3
)
SELECT id,visit_date,people FROM grouped_table T1,hinted_group_table T2 where T1.groupID = T2.groupID;

题目二：连续出现的数字

表：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 是唯一连续出现至少三次的数字。

题解

步骤一：分区并构建连续的序列

按照num分区，并按照id排序，将相同数字划分到统一窗口中，生成一个连续的排序序号。

with t1 AS (
    SELECT id, 
    num, 
    row_number() over(partition by num order by id) AS rn 
    from  Logs
    order by num asc,id asc
),

输出

| id | num | rn |
| -- | --- | -- |
| 1  | 1   | 1  |
| 2  | 1   | 2  |
| 3  | 1   | 3  |
| 5  | 1   | 4  |
| 4  | 2   | 1  |
| 6  | 2   | 2  |
| 7  | 2   | 3  |

步骤二：使用id减去连续序列

select id,num,id-rn AS rn from t1

输出

| id | num | rn |
| -- | --- | -- |
| 1  | 1   | 0  |
| 2  | 1   | 0  |
| 3  | 1   | 0  |
| 5  | 1   | 1  |
| 4  | 2   | 3  |
| 6  | 2   | 4  |
| 7  | 2   | 4  |

从上面的数据既可以看到数字1：连续出现的数字1的id减去连续的排名序列时的值都为0.

步骤三：分组统计得出次数

利用差值和num分组统计出现次数就可以得出连续出现的数字

select distinct num AS ConsecutiveNums from t1 group by num,rn having count(*) >= 3;

输出

| ConsecutiveNums |
| --------------- |
| 1               |

完整SQL

with t1 AS (
    SELECT id, 
    num, 
    row_number() over(partition by num order by id) AS rn 
    from  Logs
    order by num asc,id asc
),
t2 AS (
    select id,num,id-rn AS rn from t1
)

select distinct num AS ConsecutiveNums from t2 group by num,rn having count(*) >= 3;

其他解法

这道题还有其他解法，因为只需要统计出 连续出现至少3次的数字，所以可以通过下移来解决，如下所示：

with  t1 AS (
    select id,num,lag(num,1) over(order by id) as prev_num from Logs
),
t2 as (
    select id,num,prev_num,lag(prev_num,1) over(order by id) as prev_num2 from t1
)
select distinct num as ConsecutiveNums from t2 where num-prev_num=0 and num-prev_num2=0;

当然这种方式 有一个局限性，仅仅适用于连续出现次数比较少的场景，需要下移n-1次。