SQL Interview Prep · 课时

识别间隙与孤岛问题

Q: 「识别间隙与孤岛问题」这节课中我会学到什么？

识别文字问题中的模式，并掌握核心分组思路 你通过在浏览器中直接运行的动手代码来练习 SQL Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

识别文字问题中的模式，并掌握核心分组思路

识别间隙与孤岛问题 是 CoddyKit 上的免费 SQL Interview Prep 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 SQL Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 SQL Interview Prep 课程共包含 4 节课。

面试官正在考查的模式

当资深面试官要求您找出某种事物的连续段时，您面对的是一个间隙与岛屿问题。这个名称来自一种形象的理解：属于同一组的行构成一个岛屿，它们之间的中断则是间隙。

岛屿是根据某条规则相邻的最长连续行段（连续整数、连续日期，或重复出现的相同状态）。
间隙是两个岛屿之间缺失的部分。

能够立即识别出这类问题，本身就是资深水平的信号。许多候选人会陷入复杂的自连接写法；优雅的答案几乎总是窗口函数。

隐藏岛屿模式的题目

难点在于，面试官很少直接说“间隙与岛屿”。他们通常会把问题伪装起来。请训练自己留意这样的表述：

“找出用户持续订阅的每个时段。”
“服务器连续运行了多少天？”
“此表中缺失了哪些 ID 范围？”
“将状态相同且相邻的行合并为一行。”

这些问题的结构完全相同：将彼此相邻的行分为一组，然后报告这些组的起点、终点或缺失情况。一旦将这些表述对应到岛屿，SQL 几乎就能自然写出。

核心洞察：构造分组键

整个技巧可以用一句话概括：如果能为同一岛屿中的每一行分配相同的分组键，那么简单的 GROUP BY 就能将每个岛屿汇总为一行。

因此，任何间隙与岛屿问题真正需要做的，是计算这个分组键。不同变体的计算方式各不相同，但目标都一样。得到这个键后，最后一步就很简单：

SELECT
  grp,
  MIN(value) AS island_start,
  MAX(value) AS island_end,
  COUNT(*)   AS island_length
FROM rows_with_group_key
GROUP BY grp
ORDER BY island_start;

一个具体的数据集

让我们从数据入手。假设有一个 logins 表，用来记录用户登录的日期编号：

出现的日期编号：1、2、3、7、8、10

凭肉眼看，岛屿是{1,2,3}、{7,8}和{10}。间隙是第 4—6 天以及第 9 天。在面试中，您的任务是让数据库识别出这三个岛屿，而不是由您手动指出它们。探索每种技术时，请记住这个小数据集。

CREATE TABLE logins (day_no INT);
INSERT INTO logins VALUES (1),(2),(3),(7),(8),(10);

为什么朴素方法会失败

常见的第一反应是使用自连接，将每行与下一行比较，并标记中断位置。查找单个间隙时这种方法可行，但很快会变得难以处理：

您需要检测每个岛屿的起点和终点，这意味着需要两次扫描或两次连接。
边界行（最开始和最后的行）需要特殊处理。
如果没有更多辅助逻辑，它无法推广到“告诉我每个连续段的长度”。

面试官会关注您是会陷入自连接大战，还是能意识到一次窗口函数扫描更简洁。

间隙检测的思维模型

一种稳健的表述是：只要当前行不再与上一行相邻，就意味着一个新岛屿开始了。 使用 LAG 回看一行并进行比较。

如果 day_no - LAG(day_no) 大于 1（第一行为 NULL），则当前行开始一个新岛屿。我们用值为 1 的标记表示这种情况，否则标记为 0。看看这些标记在我们的数据中是什么样。

SELECT
  day_no,
  CASE
    WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1 THEN 0
    ELSE 1
  END AS is_new_island
FROM logins
ORDER BY day_no;

将标记转换为分组键

上一步得到的标记，对于日期编号 1、2、3、7、8、10 分别是 1、0、0、1、0、1。请注意，对这些标记求累计和，会得到一个在同一岛屿内保持不变、并在每个新岛屿处递增的数字：1、1、1、2、2、3。

这个累计和就是我们构造出的分组键。我们将标记查询包装在一个 CTE 中，再用另一个窗口函数对其求和：

WITH flagged AS (
  SELECT
    day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new_island
  FROM logins
)
SELECT
  day_no,
  SUM(is_new_island) OVER (ORDER BY day_no) AS grp
FROM flagged;

完成示例

现在在分组键之上再叠加最终的 GROUP BY。每个不同的 grp 值就是一个岛屿，我们报告它的边界和大小：

结果正是我们凭肉眼识别出的三个岛屿：1-3（长度 3）、7-8（长度 2）和 10-10（长度 1）。这个三层配方（标记、累计和、分组）是您几乎每次编写间隙与岛屿答案时都会用到的骨架。

WITH flagged AS (
  SELECT day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new
  FROM logins
),
keyed AS (
  SELECT day_no,
    SUM(is_new) OVER (ORDER BY day_no) AS grp
  FROM flagged
)
SELECT grp, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed GROUP BY grp ORDER BY start_day;

相邻关系取决于领域

不同问题之间唯一会变化的部分，是相邻的定义。识别正确的相邻规则，是识别这类问题的一半：

整数：相差恰好为 1 时相邻。
日历日期：一个日期是另一个日期的下一天时相邻（date = prev + INTERVAL '1 day'）。
状态时段：状态值与上一行相同。

骨架相同，只是 CASE 内的比较不同。判断适用哪种相邻规则，是您在面试中应该直接提出的澄清问题。

需要提出的澄清问题

在写下一行 SQL 之前，先通过澄清范围来赢得加分。关于间隙与岛屿问题，适合澄清的问题包括：

“我应该按每个用户分别处理数据，还是全局处理？”（这决定您是否要添加 PARTITION BY user_id。）
“同一天是否可能有重复值？它们会中断连续段，还是会延长连续段？”
“您需要的是岛屿、间隙，还是两者都要？”
“序列是否保证已排序，还是应由我自行排序？”

提出这些问题，说明您以前解决过这类问题，也了解它的边界情况。

使用 PARTITION BY 处理各组岛屿

真实的面试数据几乎总是按组组织，例如每个用户的登录记录。修复方式很机械：在每个窗口函数中加入 PARTITION BY user_id，这样岛屿就不会跨用户延伸。

骨架完全相同，只需进行分区。这也是为什么先掌握单数据流情况很有价值：扩展到按组处理只需改动一个子句。

SELECT
  user_id, day_no,
  CASE WHEN day_no - LAG(day_no)
         OVER (PARTITION BY user_id ORDER BY day_no) = 1
       THEN 0 ELSE 1 END AS is_new
FROM logins;

快速检查

测试您识别模式的直觉。

回顾：识别结构

现在您可以从伪装形式中识别间隙与岛屿问题，并说出相应策略：

触发词：连续、持续、不间断、连胜、缺失范围、合并相邻行。
核心思路：为同一连续段中的每一行分配相同的分组键，然后对其执行 GROUP BY。
步骤：使用 LAG 标记新岛屿，将标记累计求和得到分组键，然后聚合。
相邻关系取决于具体领域（整数、日期或未改变的状态）。
按组分析时添加 PARTITION BY；编码前先澄清范围。

接下来，我们将进一步学习最优雅的分组键构造方法：行号差值技巧。

常见问题解答

「识别间隙与孤岛问题」课时是免费的吗？

是的 — 「识别间隙与孤岛问题」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 SQL Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 SQL Interview Prep 课程共包含 4 节课。

「识别间隙与孤岛问题」这节课中我会学到什么？

识别文字问题中的模式，并掌握核心分组思路你通过在浏览器中直接运行的动手代码来练习 SQL Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 SQL Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 SQL Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 1 节课，共 4 节。

「识别间隙与孤岛问题」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 SQL Interview Prep 课中编写并运行代码吗？

能。每节 SQL Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 SQL Interview Prep