LeetCode 610. 判断三角形

2025-04-12 HGNULB 约 8 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 610. 判断三角形

题意分析

表 Triangle 有三列 x、y、z，主键是这三列的组合，每一行代表三条线段的长度。要求为每一行判断这三条线段能否构成一个三角形，并在原有三列之后额外输出一列 triangle，取值是字符串 'Yes' 或 'No'。

有两个信号决定了这题的写法。第一，输出行数与输入行数完全一致——不是筛选出能构成三角形的行，而是每一行都要保留并打上标签。这排除了 WHERE 过滤，判断逻辑必须落在 SELECT 列表里。第二，判断只依赖当前行自己的三个字段，行与行之间没有任何关系，所以不需要连接、分组、子查询或窗口函数，一次单表扫描就够。

数学侧的约束来自题面：x、y、z 都在 $1$ 到 $1000$ 之间，也就是恒为正整数。这一点很重要，它意味着不需要额外校验「边长必须大于 $0$」，判断条件可以只保留三条不等式。另外注意「两边之和大于第三边」必须是严格大于：三条线段之和相等的退化情形（比如 $1, 2, 3$）只能拼成一条直线，不构成三角形。

边界上要覆盖：退化情形（如 1 2 3，1+2 = 3 不满足严格大于）；等边（如 5 5 5，三条不等式全部成立）；长短悬殊（如 1 1 1000）；以及三个字段顺序不固定——表里并没有保证 x <= y <= z，所以不能默认最大的那条边是 z。列名必须精确输出为 x、y、z、triangle，大小写和顺序都不能改。

解法：SQL 查询建模

核心思路

一个常见的错误起点是先想「怎么找出最长边」：比如用 GREATEST(x, y, z) 取出最大值，再判断另外两边之和是否大于它。这在数学上是对的（只需检查最长边一条不等式），但在 SQL 里要么写成嵌套的 CASE，要么调用方言相关的 GREATEST 函数，可读性和可移植性都变差，而且很容易在「另外两边之和」的表达式里写错。

瓶颈在于「找最长边」这个动作本身是多余的。观察三角形不等式：判定条件是「任意两边之和大于第三边」，一共三条：$x + y > z$、$x + z > y$、$y + z > x$。当三边均为正数时，其中最长边对应的那一条是最紧的，另外两条自动成立；但反过来说，把三条全部写出来并用 AND 连接，结果与只检查最紧那一条完全等价，而且不需要事先知道哪条边最长。既然表结构没有承诺 x、y、z 的大小关系，把三条不等式全写出来才是最省心也最不会错的写法。

于是查询的结构就定死了：输出粒度是原表的每一行（不做任何聚合和过滤），在此基础上追加一个由 CASE WHEN ... THEN 'Yes' ELSE 'No' END 生成的派生列。CASE 表达式在这里承担的角色是「把布尔判定翻译成题目要求的字符串」，这是 SQL 里给每行打标签的标准手段。

需要显式说明的不变量是：结果集的行数、行序基础和前三列的取值都与 Triangle 表逐行一一对应，第四列 triangle 仅由该行自身的 x、y、z 决定。正因为这条不变量，整个查询里既不需要 JOIN（没有跨行依赖），也不需要 GROUP BY（没有聚合），更不需要 ORDER BY（题目对返回顺序无要求）。

解题步骤

先确定输出粒度是「每一行一条结果」，据此把主表 Triangle 直接放进 FROM，不引入任何连接或子查询。理由：判定条件只依赖当前行的三个字段，引入连接只会产生笛卡尔积或重复行，把简单问题复杂化。

在 SELECT 列表里原样输出 x、y、z 三列。理由：题目要求结果保留原始三列且列名不变，任何重命名或重排都会导致判题失败。

追加第四列，用 CASE WHEN 条件 THEN 'Yes' ELSE 'No' END。理由：判断结果要作为每行的一个值出现，而不是作为过滤条件，所以必须写在 SELECT 里；CASE 是 SQL 中把布尔表达式映射成任意字面量的标准结构，比 IF() 更通用（IF 是 MySQL 方言，CASE 是标准 SQL）。

条件写成 x + y > z AND x + z > y AND y + z > x，三条不等式全部用严格大于并用 AND 串联。理由：表结构不保证三列有序，不能假设 z 是最长边；三条一起写既覆盖了所有排列，又避免了 GREATEST 这类方言函数。用严格大于而非 >=，是因为等号成立时三点共线，不构成三角形。

用 AS triangle 显式给派生列命名。理由：不加别名时列名会是整个 CASE 表达式的文本，与题目要求的 triangle 不符，判题会直接判错。

不写 WHERE，也不写 ORDER BY。理由：加 WHERE 会把 'No' 的行过滤掉，输出行数变少；题目明确说返回顺序不限，多余的排序只会增加执行成本。

以表中三行 (13, 15, 30)、(10, 20, 15)、(1, 2, 3) 走一遍。第一行：13 + 15 = 28，不大于 30，第一条不等式就为假，AND 短路，输出 'No'——注意这里最长边是 z，恰好被第一条不等式抓住。第二行：10 + 20 = 30 > 15 成立，10 + 15 = 25 > 20 成立，20 + 15 = 35 > 10 成立，三条全真，输出 'Yes'——这行的最长边是 y 而不是 z，起决定作用的是第二条不等式，这正是「必须三条全写」的理由。第三行：1 + 2 = 3，不严格大于 3，输出 'No'——如果把 > 误写成 >=，这行会被错判为 'Yes'。最终结果集是三行四列，行数与原表一致，前三列原样保留。

代码实现

SELECT
    x,
    y,
    z,
    CASE
        WHEN x + y > z AND x + z > y AND y + z > x THEN 'Yes'
        ELSE 'No'
    END AS triangle
FROM Triangle;

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是 Triangle 表的行数。执行计划是一次全表扫描，每行只做三次加法、三次比较和一次 CASE 求值，都是常数代价；没有连接、分组和排序，因此不会出现 $O(n^2)$ 的嵌套循环或 $O(n \log n)$ 的排序开销。

空间复杂度：$O(1)$ 的额外空间（不计结果集本身）。查询是流式的，逐行读入、逐行输出，不需要哈希表、排序缓冲或临时中间表；结果集大小与输入同阶，是 $O(n)$，但那是必须返回的数据。

关键点总结

区分「筛选」和「打标签」是 SQL 建模的第一步：要减少行数就写 WHERE，要保留全部行只是加一列结论就写 CASE。看到题目说「输出每一行并标注」，就该立刻锁定 CASE 而不是 WHERE。

当判定条件在数学上有「只需检查最紧的那一条」这类优化，但字段间的大小顺序没有被表结构保证时，把所有对称条件都列出来往往比先排序再判断更划算——代价只是常数倍的比较，换来的是不依赖方言函数、不需要额外推理。

派生列一定要用 AS 显式命名。SQL 题的判题通常同时比对列名和列序，这类「答案对但列名错」的失分完全可以避免。

> 与 >= 的选择要回到问题的数学定义上确认，而不是凭手感。三角形不等式的严格性正是这题唯一的陷阱点，退化成直线的情形必须判 'No'。

面试视角：字节和美团用这题考的是能否把业务规则准确翻译成 SQL 表达式，而不是查询优化。作答时先口头确认「输出行数等于输入行数」这条关键约束，再说明「因为列间无序所以三条不等式全写」，最后一句话点出严格大于的退化用例。如果面试官追问「能不能只写一条不等式」，正确回答是：可以，用 x + y + z > 2 * GREATEST(x, y, z)，但这依赖 MySQL 的 GREATEST 函数，可移植性差，工程上不如三条 AND 直白。

易错点总结

错误写法：把判定写进 WHERE x + y > z AND x + z > y AND y + z > x 而不是 SELECT 里 → 用例表中有 (1, 2, 3) 这行 → 该行被过滤掉，结果集只剩能构成三角形的行，行数与输入不一致，判题直接失败。

错误写法：不等式用 >= → 用例 (1, 2, 3) → 1 + 2 >= 3 成立，三条全真，输出 'Yes'，但三点共线不构成三角形，正确答案是 'No'。

错误写法：只写一条 x + y > z，默认 z 是最长边 → 用例 (10, 20, 15) → 10 + 20 = 30 > 15 成立就直接输出 'Yes'；换成 (10, 2, 5) 时 10 + 2 = 12 > 5 也成立，输出 'Yes'，但最长边是 x，2 + 5 = 7 并不大于 10，正确答案是 'No'。

错误写法：三条不等式之间用 OR 连接 → 用例 (1, 1, 1000) → 1 + 1000 > 1 这条成立，OR 短路为真，输出 'Yes'，但正确答案是 'No'；必须用 AND 要求三条同时成立。

错误写法：忘记写 AS triangle → 用例任意输入 → 派生列名变成 CASE WHEN x + y > z ... 这一长串表达式文本，与题目要求的列名 triangle 不符，结果被判错。

错误写法：返回值写成布尔或数字，例如 CASE WHEN ... THEN 1 ELSE 0 END → 用例 (5, 5, 5) → 输出 1 而不是字符串 'Yes'，类型和字面量都与要求不符。

错误写法：把 'Yes' / 'No' 写成 "Yes" / "No"（双引号）→ 用例在 ANSI SQL 模式或 PostgreSQL 下执行 → 双引号被解析为标识符（列名）而非字符串字面量，报错「列 Yes 不存在」；SQL 字符串必须用单引号。

错误写法：为了「保险」加上 AND x > 0 AND y > 0 AND z > 0 → 用例任意输入 → 结果虽然不会错，但题目已保证边长在 $1$ 到 $1000$，多写三个恒真条件只是噪声；更糟的变体是把这三个条件写进 WHERE，那就退化成上面的过滤错误。

错误写法：为了取最长边引入自连接 FROM Triangle t1, Triangle t2 → 用例表中有 $n$ 行 → 产生 $n^2$ 行笛卡尔积，输出行数暴增且完全错误，同时执行成本从 $O(n)$ 退化到 $O(n^2)$。

错误写法：用 SELECT * 加派生列 → 用例表结构未来新增字段时 → 结果列数与要求不符；即便当前只有三列，显式列出 x, y, z 也是更稳的写法。

相似题目

题目	难度	考察点
175. 组合两个表	简单	输出粒度同样固定为左表每一行，但要靠 `LEFT JOIN` 保留无匹配行
181. 超过经理收入的员工	简单	判定条件跨行，需要自连接把员工与经理配成一对再比较
182. 查找重复的电子邮箱	简单	判定依赖聚合结果，条件必须写在 `HAVING` 而不是 `WHERE` 或 `SELECT`
197. 上升的温度	简单	自连接的连接条件是日期相差一天，考察日期函数与连接谓词的写法
180. 连续出现的数字	中等	需要看连续三行是否相同，靠三表自连接或窗口函数，且结果要去重