LeetCode 面试题 16.03. 交点
目录
题目描述
题意分析
给的是两条线段，不是两条直线：每条线段由起点和终点两个整点确定，问它们有没有公共点。有就返回一个公共点的坐标，没有就返回空数组。
题目里最容易被忽略的一句是「如果有多个交点，返回 $x$ 值最小的那个；$x$ 相同时返回 $y$ 值最小的那个」。这句话直接告诉你：交点不一定唯一。两条线段可以整段重合或部分重合，此时公共点有无穷多个，必须挑出那个字典序最小的端点，所以答案不能只考虑「一个点」的情形。
约束信号有两层。坐标是整数且绝对值可以到 $2^{31}-1$，这意味着任何形如「差乘差」的中间量都能达到 $2^{62}$ 量级，用 32 位整数计算必然溢出；同时输出的交点坐标不一定是整数（两条斜着的线段交在半格上），所以最终得用浮点表示并配合误差阈值比较。
边界情况要提前列全：线段可能垂直于 $x$ 轴，斜率不存在；线段的起点和终点可能是同一个点，退化成一个孤立的点；两条线段可能平行且不共线、共线但不重叠、共线且只在一个端点相碰；交点也可能恰好落在某条线段的端点上，这属于有交点。
解法：直线交点 + 线段判定
核心思路
连续的点无法枚举，所以没有真正意义上的「暴力解」，只能走解析几何。第一个坑是斜率式 $y=kx+b$：竖直线段的斜率不存在，一上来就要为它单开分支。改用一般式 $Ax+By=C$ 就没有这个问题，对由 $(x_1,y_1)$ 和 $(x_2,y_2)$ 决定的直线取 $A=y_2-y_1$、$B=x_1-x_2$、$C=Ax_1+By_1$，竖直和水平都被统一进来。
两条直线的交点就是二元一次方程组的解，记 $d=A_1B_2-A_2B_1$。当 $d\neq 0$ 时解唯一，由克拉默法则得 $x=\dfrac{C_1B_2-C_2B_1}{d}$、$y=\dfrac{A_1C_2-A_2C_1}{d}$。但这是直线的交点，未必落在两条线段上，所以还要回头验证它同时位于两条线段的包围盒内——因为该点已经在两条直线上，落进包围盒就等价于落在线段上。
当 $d=0$ 时两条直线平行。此时要么完全不相交，要么两条线段共线。判共线只需检查一个端点是否在另一条直线上，即三点叉积为零；但如果某条线段退化成一个点，它「所在的直线」并不存在，单向检查会误判，所以两个方向的叉积都要为零才算共线。
共线之后，问题降到一维：求两个区间的交。这里用一条不变量把它做干净——先把每条线段的两个端点按 $(x,y)$ 字典序排成
start ≤ end；对同一条直线上的点，字典序恰好是沿该直线单调的顺序（水平方向有分量时按 $x$ 单调，纯竖直时按 $y$ 单调）。于是重叠区间的左端就是 $\max(\text{start}_1,\text{start}_2)$、右端就是 $\min(\text{end}_1,\text{end}_2)$，二者比较即可判空；而左端本身就是字典序最小的公共点，正好是题目要的答案。
解题步骤
- 把四个整点转成浮点点对，并对每条线段的两个端点按字典序交换，保证
start ≤ end。为什么先排：后面共线求交完全依赖这个顺序，排好之后「取较大的起点、较小的终点」才成立。- 用 $A=y_2-y_1$、$B=x_1-x_2$、$C=Ax_1+By_1$ 分别求出两条直线的一般式系数。为什么用一般式：避开竖直线段斜率不存在的分支。
- 计算 $d=A_1B_2-A_2B_1$，用
abs(d) < EPS判断是否平行。为什么不能写d == 0：系数已经是浮点数，直接比相等在有除法参与的场景下不可靠，统一用阈值更安全。- 若不平行，按克拉默法则解出交点，再检查它是否同时落在两条线段的包围盒里（比较时两端各放宽
EPS）。为什么只查包围盒就够：该点必在两条直线上，直线上的点落进线段的包围盒当且仅当它在线段上。- 若平行，先算两个方向的叉积
cross(a1,a2,b1)与cross(b1,b2,a1)，任一不为零就直接返回空。为什么要两个方向：只查一个方向时，退化成点的那条线段叉积恒为零，会把任意位置的孤点误判成共线。- 共线时取
maxStart = max(a1,b1)、minEnd = min(a2,b2)，若maxStart > minEnd则两段不重叠返回空，否则返回maxStart。为什么返回的就是答案：它是重叠区间字典序最小的端点，与题目「$x$ 最小、$x$ 同则 $y$ 最小」的要求完全一致。以
start1=[0,0]、end1=[1,0]、start2=[1,1]、end2=[0,-1]走一遍：第一条线段 $(0,0)$ 不大于 $(1,0)$，不交换；第二条线段 $(1,1)$ 的 $x$ 大于 $(0,-1)$ 的 $x$，交换后得到 $b_1=(0,-1)$、$b_2=(1,1)$。第一条直线 $A_1=0-0=0$、$B_1=0-1=-1$、$C_1=0\times 0+(-1)\times 0=0$，即 $-y=0$。第二条直线 $A_2=1-(-1)=2$、$B_2=0-1=-1$、$C_2=2\times 0+(-1)\times(-1)=1$，即 $2x-y=1$。$d=0\times(-1)-2\times(-1)=2\neq 0$，不平行。解得 $x=\dfrac{0\times(-1)-1\times(-1)}{2}=0.5$，$y=\dfrac{0\times 1-2\times 0}{2}=0$。检查包围盒：第一条线段 $x\in[0,1]$、$y\in[0,0]$，$(0.5,0)$ 通过；第二条线段 $x\in[0,1]$、$y\in[-1,1]$，同样通过。返回 $[0.5,0]$。再看一组落进平行分支的输入
start1=[0,0]、end1=[3,3]、start2=[1,1]、end2=[2,2]：$A_1=3,B_1=-3,C_1=0$，$A_2=1,B_2=-1,C_2=0$，$d=3\times(-1)-1\times(-3)=0$。两个方向的叉积都为零，确认共线。maxStart在 $(0,0)$ 与 $(1,1)$ 中取较大者得 $(1,1)$，minEnd在 $(3,3)$ 与 $(2,2)$ 中取较小者得 $(2,2)$，$(1,1)\le(2,2)$ 说明区间非空，返回 $[1,1]$。
代码实现
// 非平行时计算直线交点，再判断是否落在两条线段内。
class Solution {
private static final double EPS = 1e-9;
public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
double[] a1 = toPoint(start1);
double[] a2 = toPoint(end1);
double[] b1 = toPoint(start2);
double[] b2 = toPoint(end2);
if (greater(a1, a2)) {
swap(a1, a2);
}
if (greater(b1, b2)) {
swap(b1, b2);
}
double A1 = a2[1] - a1[1];
double B1 = a1[0] - a2[0];
double C1 = A1 * a1[0] + B1 * a1[1];
double A2 = b2[1] - b1[1];
double B2 = b1[0] - b2[0];
double C2 = A2 * b1[0] + B2 * b1[1];
double det = A1 * B2 - A2 * B1;
if (Math.abs(det) < EPS) {
if (Math.abs(cross(a1, a2, b1)) > EPS || Math.abs(cross(b1, b2, a1)) > EPS) {
return new double[0];
}
double[] maxStart = a1;
if (greater(b1, a1)) {
maxStart = b1;
}
double[] minEnd = a2;
if (greater(a2, b2)) {
minEnd = b2;
}
if (greater(maxStart, minEnd)) {
return new double[0];
}
return maxStart;
}
double x = (C1 * B2 - C2 * B1) / det;
double y = (A1 * C2 - A2 * C1) / det;
double[] p = new double[]{x, y};
if (onSegment(p, a1, a2) && onSegment(p, b1, b2)) {
return p;
}
return new double[0];
}
private boolean onSegment(double[] p, double[] s, double[] e) {
return p[0] >= Math.min(s[0], e[0]) - EPS && p[0] <= Math.max(s[0], e[0]) + EPS
&& p[1] >= Math.min(s[1], e[1]) - EPS && p[1] <= Math.max(s[1], e[1]) + EPS;
}
private double cross(double[] a, double[] b, double[] c) {
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
}
private boolean greater(double[] p, double[] q) {
return p[0] > q[0] || (Math.abs(p[0] - q[0]) < EPS && p[1] > q[1]);
}
private double[] toPoint(int[] p) {
return new double[]{p[0], p[1]};
}
private void swap(double[] a, double[] b) {
double t0 = a[0];
double t1 = a[1];
a[0] = b[0];
a[1] = b[1];
b[0] = t0;
b[1] = t1;
}
}
// 非平行时计算直线交点，再判断是否落在两条线段内。
func intersection(start1 []int, end1 []int, start2 []int, end2 []int) []float64 {
const eps = 1e-9
p1 := []float64{float64(start1[0]), float64(start1[1])}
p2 := []float64{float64(end1[0]), float64(end1[1])}
p3 := []float64{float64(start2[0]), float64(start2[1])}
p4 := []float64{float64(end2[0]), float64(end2[1])}
if greater(p1, p2, eps) {
swapPoint(p1, p2)
}
if greater(p3, p4, eps) {
swapPoint(p3, p4)
}
A1 := p2[1] - p1[1]
B1 := p1[0] - p2[0]
C1 := A1*p1[0] + B1*p1[1]
A2 := p4[1] - p3[1]
B2 := p3[0] - p4[0]
C2 := A2*p3[0] + B2*p3[1]
det := A1*B2 - A2*B1
if math.Abs(det) < eps {
if math.Abs(cross(p1, p2, p3)) > eps || math.Abs(cross(p3, p4, p1)) > eps {
return []float64{}
}
maxStart := p1
if greater(p3, p1, eps) {
maxStart = p3
}
minEnd := p2
if greater(p2, p4, eps) {
minEnd = p4
}
if greater(maxStart, minEnd, eps) {
return []float64{}
}
return []float64{maxStart[0], maxStart[1]}
}
x := (C1*B2 - C2*B1) / det
y := (A1*C2 - A2*C1) / det
p := []float64{x, y}
if onSegment(p, p1, p2, eps) && onSegment(p, p3, p4, eps) {
return p
}
return []float64{}
}
func onSegment(p []float64, a []float64, b []float64, eps float64) bool {
return p[0] >= math.Min(a[0], b[0])-eps && p[0] <= math.Max(a[0], b[0])+eps &&
p[1] >= math.Min(a[1], b[1])-eps && p[1] <= math.Max(a[1], b[1])+eps
}
func cross(a []float64, b []float64, c []float64) float64 {
return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
}
func greater(p []float64, q []float64, eps float64) bool {
return p[0] > q[0] || (math.Abs(p[0]-q[0]) < eps && p[1] > q[1])
}
func swapPoint(a []float64, b []float64) {
a[0], b[0] = b[0], a[0]
a[1], b[1] = b[1], a[1]
}
复杂度分析
- 时间复杂度：$O(1)$，凭据：输入固定是四个点，整个过程只有若干次加减乘除和比较，不存在任何随规模增长的循环。
- 空间复杂度：$O(1)$，凭据：只额外开了四个二维点和六个直线系数，全是常数个标量。
关键点总结
- 涉及直线的题一律用一般式 $Ax+By=C$，不要用 $y=kx+b$。前者天然容纳竖直线，能省掉一整类特判，也避免斜率无穷大带来的数值爆炸。
- 「直线求交」和「点在线段上」是两件事，必须分两步：先解方程得候选点，再验证它落在两条线段的范围内。跳过第二步就把线段悄悄当成了直线。
- 遇到平行分支不要急着返回空，先确认是否共线。共线时问题从二维退化成一维区间求交，这个降维是本题的核心技巧。
- 端点先按字典序规范化，可以让「取重叠区间左端」同时解决求交和选最优答案两件事，省掉一次额外的比较逻辑。
- 面试视角：面试官几乎必然会追问退化情形——线段退化成点、两点重合、交点恰在端点。能主动把「单向叉积判共线对退化线段失效、需要双向检查」讲出来，是这题少数几个能明确区分候选人的地方。
- 面试视角：另一个高频追问是精度。要能说清坐标范围导致中间乘积达到 $2^{62}$ 量级，因此不能用
int承接，且浮点比较必须用EPS而不是==；如果面试官要求严格正确，可以提出用long做整数叉积判断相交性、只在最后求点时才转浮点。
易错点总结
- 错误写法：用 $y=kx+b$ 建模，靠
if (x1 == x2)单独处理竖直线段。用例start1=[0,0], end1=[0,5]→ 斜率分母为零，若忘了这个分支就得到无穷大或NaN，后续所有比较全部失效。- 错误写法：平行分支只检查一个方向的叉积
cross(a1,a2,b1)。用例start1=end1=[1,5]、start2=[0,0]、end2=[2,2]→ 第一条线段退化成点使叉积恒为零，被误判成共线，进而返回 $(1,5)$，而正确答案是无交点。- 错误写法：把直线交点算完就直接返回，不检查它是否在线段范围内。用例
start1=[0,0], end1=[1,1], start2=[5,4], end2=[6,4]→ 两条直线交于 $(4,4)$，但该点不在任何一条线段上，正确答案是空。- 错误写法：用
int计算 $C=Ax_1+By_1$。用例坐标取到 $2\times 10^9$ 量级 → 乘积远超 32 位范围直接溢出，得到一个符号都可能相反的系数，判平行和求交全错。- 错误写法：判平行时写
if (det == 0)。用例任意由浮点乘减得到的近似零 → 由于舍入det可能是 $10^{-16}$ 这样的极小非零值，程序错误地走进「不平行」分支去做除法，解出一个绝对值极大的伪交点。- 错误写法：共线重叠时随手返回某条线段的起点。用例
start1=[0,0], end1=[3,3], start2=[1,1], end2=[2,2]→ 返回 $(0,0)$，但它不在第二条线段上；正确答案是两个起点中较大的 $(1,1)$。- 错误写法：忘记先把端点按字典序规范化就直接取
max(start)与min(end)。用例start2=[2,2], end2=[1,1]→ 起点反而比终点大，区间判空条件立刻成立，明明重叠却返回空。- 错误写法：包围盒判定写成严格不等号
p[0] > min && p[0] < max。用例两条线段恰好在端点 $(1,1)$ 相碰 → 交点落在边界上被判为不在线段内，返回空，而端点相碰是有交点的。- 错误写法：认为「多个交点」只会发生在两段完全重合时。用例
start1=[0,0], end1=[3,3], start2=[1,1], end2=[5,5]→ 部分重叠同样有无穷多交点，重叠区间是 $[(1,1),(3,3)]$，仍需返回其中最小的 $(1,1)$。- 错误写法：把「返回空」实现成返回
null或长度不为零的数组。用例任意无交点输入 → 判定按空数组比对，返回null会抛异常，返回[0,0]则被当成有交点，两种都算错。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 149. 直线上最多的点数 | 困难 | 用叉积代替斜率判共线，避开除法与精度 |
| 223. 矩形面积 | 中等 | 一维区间求交的二维版本，重叠长度乘法 |
| 593. 有效的正方形 | 中等 | 只用距离的平方判形状，全程停留在整数域 |
| 836. 矩形重叠 | 简单 | 把二维重叠拆成两个方向的区间是否相交 |
| 1401. 圆和矩形是否有重叠 | 中等 | 点到矩形的最近点，考察夹逼取值 |
| 面试题 16.13. 平分正方形 | 中等 | 同样要处理竖直线与字典序最小的输出规则 |
| 面试题 16.14. 最佳直线 | 中等 | 枚举点对定直线，比较时需保证下标字典序最小 |