LeetCode 183. 从不订购的客户

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

题目描述

✅ 183. 从不订购的客户

题意分析

Customers(id, name) 保存客户，Orders(id, customerId) 保存订单。要求找出在 Orders 中不存在任何匹配记录的客户，并把客户名输出为 Customers。

这是典型的反连接（anti join）问题：结果粒度仍是客户，但筛选条件不是某个订单字段的值，而是“关联集合为空”。最直接的表达是相关子查询 NOT EXISTS；也可以左连接后筛选右表主键为 NULL。

不推荐 NOT IN (SELECT customerId FROM Orders)。SQL 使用三值逻辑：如果子查询结果里含有一个 NULL，表达式会变成类似 2 NOT IN (1, NULL)，其中与 NULL 的比较结果是 UNKNOWN，整条记录不会通过 WHERE，甚至可能导致结果为空。NOT EXISTS 和左反连接都没有这个陷阱。

官方样例中订单只属于客户 1（Joe）和 3（Sam），所以客户 2（Henry）和 4（Max）的关联订单集合为空，应被输出。

解法一：NOT EXISTS 相关子查询

核心思路

对 Customers 的每一行 c，相关子查询只回答一个布尔问题：是否存在 o.customerId = c.id 的订单。

NOT EXISTS 保留答案为“不存在”的客户。子查询写 SELECT 1 即可，因为数据库只关心是否至少有一行命中，不需要读取订单的具体列；优化器通常会把它改写成高效的 anti join，并在找到第一条匹配订单后停止继续搜索该客户。

行级不变量是：输出的每个客户，都不存在一条能通过 o.customerId = c.id 条件的订单记录。订单表中其它客户的记录以及 NULL customerId 都不会影响这个判断。

解题步骤

  • 扫描 Customers AS c，因为输出对象是客户。
  • 在相关子查询中按 o.customerId = c.id 查找订单。
  • 用 NOT EXISTS 反转“存在匹配订单”的条件。
  • 输出 c.name 并按题目要求命名为 Customers。

代码实现

SELECT c.name AS Customers
FROM Customers AS c
WHERE NOT EXISTS (
    SELECT 1
    FROM Orders AS o
    WHERE o.customerId = c.id
);

复杂度分析

设客户数为 $C$、订单数为 $O$。实际复杂度取决于执行计划：

  • 若 Orders(customerId) 有 B-tree 索引，每位客户可做一次索引存在性查询，约为 $O(C \log O)$，命中后可短路。
  • 优化器使用哈希反连接时，时间通常为 $O(C + O)$，构建订单客户集合需要 $O(O)$ 临时空间。
  • 若没有索引也没有合适的连接改写，相关子查询的朴素最坏情况是 $O(CO)$。

关键点总结

  • “找没有关联记录的主表行”优先想到 NOT EXISTS，它最直接表达集合不存在。
  • EXISTS 只关心是否有行，SELECT 1 比选择实际业务列更能表达意图。
  • 同一客户有多少张订单不影响答案；找到一张就足以排除，因此无需 GROUP BY 或 COUNT。
  • NOT EXISTS 对子查询中的 NULL 安全，这是它相对 NOT IN 的重要工程优势。
  • 高频索引追问：应在 Orders(customerId) 上建索引，而不是只依赖订单主键 id。

解法二：LEFT JOIN 构造反连接

核心思路

先把所有客户左连接到订单。没有订单的客户仍会产生一行，但这一行的所有订单列都为 NULL；随后筛选右表主键 o.id IS NULL，就只留下未匹配客户。

必须检测一个确定非空的右表列。Orders.id 是主键，真实订单行不可能为 NULL，所以它能可靠地区分“未匹配补出的 NULL”和“匹配到一条业务记录”。

代码实现

SELECT c.name AS Customers
FROM Customers AS c
LEFT JOIN Orders AS o
    ON o.customerId = c.id
WHERE o.id IS NULL;

复杂度分析

物理代价与 NOT EXISTS 类似：哈希反连接通常为 $O(C+O)$ 时间、$O(O)$ 临时空间；使用 Orders(customerId) 索引时约为 $O(C \log O)$。具体由优化器决定。

解法对比

写法 NULL 安全 语义 面试建议
NOT EXISTS 是 直接表达“匹配集合不存在” 首选，意图最清晰
LEFT JOIN ... IS NULL 是 先保留全部客户，再筛未匹配行 同样正确，适合展示外连接理解
NOT IN 否，除非显式排除子查询中的 NULL 集合排除 本题不推荐作为默认答案

易错点总结

  • 直接使用 NOT IN：若订单客户集合为 (1, 3, NULL)，Henry 的 2 NOT IN (...) 结果是 UNKNOWN 而不是 TRUE，会被错误过滤。
  • 使用 INNER JOIN：它只保留有订单的客户，得到的恰好是题目答案的反面。
  • 左连接后写 WHERE o.customerId IS NOT NULL：这会保留已匹配订单，同样把逻辑写反；未订购客户应检查 o.id IS NULL。
  • 把 o.id IS NULL 放进 ON：由于真实订单主键不为空，连接条件永远匹配不到，所有客户都会被当成未订购。空值筛选必须发生在连接结果的 WHERE 阶段。
  • 用 COUNT(*) = 0 但没有正确分组：左连接对未匹配客户也会生成一行，COUNT(*) 是 1 而不是 0；若走聚合方案必须数右表非空列 COUNT(o.id)，但这比反连接更绕。
  • 无依据地加 DISTINCT c.name：不同客户可能同名，题目按客户 ID 判断是否订购；DISTINCT 会错误合并两个真实客户。

相似题目

题目 难度 考察点
175. 组合两个表 简单 左连接保留主表全部行，是本题左反连接的基础
584. 寻找用户推荐人 简单 直接考查 SQL 三值逻辑以及 NULL 条件写法
607. 销售员 简单 多表关联后排除与指定公司有订单的销售员
1978. 上级经理已离职的公司员工 简单 在同表关系中找引用对象不存在的记录