LeetCode 175. 组合两个表

约 4 分钟
文章信息 2 个分类 1 个标签
分类
LeetCode 简单
标签
数据库
目录

题目描述

✅ 175. 组合两个表

题意分析

有两张表：Person 保存人员的 personId、姓和名，Address 保存某个 personId 对应的城市和州。要求报告 Person 表中的每个人，即使某个人没有地址，也要输出这一行，并让 city、state 显示为 NULL。

输出粒度由 Person 决定，因此 Person 必须是连接的保留表。普通 INNER JOIN 只返回两边都匹配的人员，会把没有地址的人直接删除；LEFT JOIN 才能保留左表全部行，并在右表未匹配时自动补 NULL。

连接键是两张表共同表达人员身份的 personId，不是各自主键名称中看起来相似的 addressId。查询不需要聚合、分组或去重，题目也允许任意输出顺序。

官方样例中 Person 有 Allen（personId = 1）和 Bob（personId = 2），Address 只有 personId = 2 的纽约地址。左连接后 Allen 仍然保留，其城市和州为 NULL；Bob 得到匹配地址。

解法：以 Person 为主表做 LEFT JOIN

核心思路

从 Person AS p 开始，对每一行按 p.personId = a.personId 到 Address AS a 中查找匹配记录。

LEFT JOIN 的行级不变量是：每一条 Person 记录至少产生一条结果行。找到地址就填入右表字段；找不到时，右表投影出的 a.city、a.state 自动为 NULL。

显式写 ON 条件比 USING (personId) 更适合面试表达：它直接展示两张表各自参与连接的列，也便于后续增加其它连接条件。

解题步骤

  • 把 Person 作为左表，因为题目要求其中每个人都必须出现。
  • 用 p.personId = a.personId 建立人员与地址的关联。
  • 选择 p.firstName、p.lastName 和右表的 a.city、a.state。
  • 不添加会过滤右表空值的 WHERE 条件，也不需要 GROUP BY 或 ORDER BY。

代码实现

SELECT
    p.firstName,
    p.lastName,
    a.city,
    a.state
FROM Person AS p
LEFT JOIN Address AS a
    ON a.personId = p.personId;

复杂度分析

设 Person、Address 的行数分别为 $P$、$A$，输出行数为 $R$。SQL 的物理复杂度取决于执行计划：

  • 使用哈希连接时，典型时间复杂度为 $O(P + A + R)$，构建哈希表需要 $O(A)$（或由优化器选择较小表）额外空间。
  • 若 Address(personId) 上有 B-tree 索引，扫描 Person 并逐行查找的代价约为 $O(P \log A + R)$；索引本身属于数据库存储，不计作查询临时空间。
  • 没有可用索引且优化器选择嵌套循环时，最坏可能退化为 $O(PA)$。因此面试中不应脱离索引和执行计划笼统声称固定为 $O(n)$。

关键点总结

  • 先问“结果必须保留哪张表的全部对象”，它直接决定左连接的方向。
  • LEFT JOIN 未匹配时会自然产生 NULL，无需用 CASE 手动补空值。
  • ON 决定两表如何匹配，WHERE 决定连接结果哪些行最终保留；二者位置不同会改变外连接语义。
  • 若一个人可以拥有多条地址，左连接会为该人输出多行。这不是 SQL 自动产生的重复，而是“一对多”关系的真实展开；若业务只允许一个地址，应由唯一约束或额外选取规则保证。
  • 面试追问索引时，应优先考虑 Address(personId)，因为它是右表的连接查找列。

易错点总结

  • 使用 INNER JOIN：样例中的 Allen 在 Address 没有匹配行，会被直接删掉，而题目要求输出 Allen 和两个 NULL。
  • 把表的顺序写反：Address LEFT JOIN Person 保留的是所有地址，无法保证所有人员出现。
  • 连接 p.personId = a.addressId：两个列都是整数且样例可能偶然相同，查询能运行却表达了错误业务关系；正确外键是 a.personId。
  • 在 WHERE 中写 a.city = ...：没有地址的行其 a.city 为 NULL，条件结果不是 TRUE，会被过滤，使左连接退化为内连接。若条件属于“哪些地址可匹配”，应放入 ON。
  • 使用 SELECT *：会多输出 ID 等题目未要求的列，还会引入同名字段歧义。
  • 无依据地加 DISTINCT：它可能掩盖一对多关系，增加去重开销，也没有解决重复产生的业务原因。

相似题目

题目 难度 考察点
183. 从不订购的客户 简单 用反连接保留左表中没有匹配行的对象
577. 员工奖金 简单 左连接后结合 NULL 条件筛选可选关联记录
181. 超过经理收入的员工 简单 同一张表自连接，区分员工行与经理行
570. 至少有 5 名直接下属的经理 中等 自连接后按经理聚合，与本题单纯投影形成对照