如何求平面上最多有多少个点在同一直线上？（LeetCode 149）

简化版

枚举每个点作为基准点，统计其他点相对它的斜率。和基准点斜率相同的点都在同一条直线上，取最大计数即可。为了避免浮点误差，斜率不要用 double，而是用约分后的 (dy, dx) 表示，并用最大公约数归一化。

例如从点 (1,1) 看 (2,2) 和 (3,3)，斜率都可归一化为 (1,1)，说明它们在同一直线上。时间复杂度 O(n^2)，空间复杂度 O(n)。

详细版

int maxPoints(int[][] points) {
    int n = points.length;
    if (n <= 2) return n;
    int ans = 2;

    for (int i = 0; i < n; i++) {
        Map<String, Integer> map = new HashMap<>();
        int best = 0;
        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
            if (dx == 0) {
                dy = 1;
            } else if (dy == 0) {
                dx = 1;
            } else {
                int g = gcd(Math.abs(dx), Math.abs(dy));
                dx /= g;
                dy /= g;
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                }
            }
            String key = dy + "/" + dx;
            int cnt = map.getOrDefault(key, 0) + 1;
            map.put(key, cnt);
            best = Math.max(best, cnt);
        }
        ans = Math.max(ans, best + 1);
    }
    return ans;
}

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

best 统计的是除基准点外，同一斜率下最多有几个点，所以更新答案时要 best + 1，把基准点也算进去。

完整版教学

一、为什么枚举基准点

一条直线可以由两个点确定。如果我们固定一个点 points[i]，那么所有与它共线的其他点，会共享同一个斜率。因此问题可以转化为：对每个基准点，统计其他点相对它的斜率频次，最大频次加 1 就是经过该基准点的最多共线点数。

基准点 A(1,1)
B(2,2): dy=1, dx=1, slope=1/1
C(3,3): dy=2, dx=2, slope=1/1
D(1,3): 垂直线

相同 slope=1/1 的 B、C 和 A 共线，共 3 个点

二、为什么不能用 double 表示斜率

斜率是 dy / dx，看似可以用浮点数，但浮点数会有精度误差。比如某些大整数坐标下，两个本应不同的斜率可能被舍入到同一个 double，或者同一个斜率因为计算误差比较不相等。

更稳定的做法是用分数形式 (dy, dx)，并约分到最简形式。例如 (2,4) 和 (1,2) 都归一化成 (1,2)。

几何题里只要涉及“比较斜率是否相等”，优先考虑整数归一化，而不是浮点比较。

三、斜率归一化的细节

对 dy 和 dx 同除以它们绝对值的最大公约数：

int g = gcd(Math.abs(dx), Math.abs(dy));
dx /= g;
dy /= g;

然后统一符号：可以规定 dx 永远为正。如果 dx < 0，就同时翻转 dx 和 dy。这样 (1, -1) 和 (-1, 1) 不会被当成两个不同斜率。

四、水平线和垂直线要单独处理

垂直线 dx=0，斜率无穷大，不能进入普通分数约分；水平线 dy=0，要统一成 (0,1)，避免 (0,2)、(0,-3) 产生不同 key。

线型	原始情况	归一化表示
垂直线	`dx=0`	`(dy,dx)=(1,0)`
水平线	`dy=0`	`(dy,dx)=(0,1)`
普通线	`dx!=0 && dy!=0`	约分并统一 `dx>0`

这些规则必须互斥，否则可能出现除以 0 或符号不一致。

五、哈希统计的含义

对每个基准点创建一个新的哈希表。key 是归一化后的斜率，value 是在这个基准点下具有该斜率的其他点数量。

points = [(1,1), (2,2), (3,3), (2,0)]
i = (1,1)

slope 1/1 -> 2 个点: (2,2), (3,3)
slope -1/1 -> 1 个点: (2,0)

best = 2
答案候选 = best + 1 = 3

每换一个基准点，哈希表必须清空，因为斜率是相对当前基准点定义的。

六、复杂度分析

外层枚举 n 个基准点，内层枚举其后的点，整体是 O(n^2)。每次斜率归一化需要 gcd，坐标范围固定时可视为常数；严格说是 O(log C)，其中 C 是坐标差的最大绝对值。空间上每个基准点的哈希表最多记录 O(n) 个斜率。

七、重复点怎么处理

LeetCode 149 的常见版本中点坐标可能没有重复，但面试扩展时可能会追问重复点。如果允许重复点，重复点与基准点重合，不能形成斜率，需要单独计数 same。最终答案应是 best + same + 1。

基准 A(1,1)
重复点 A'(1,1): same=1
B(2,2), C(3,3): slope=1/1, best=2
总数 = 基准 A + same + best = 1 + 1 + 2 = 4

如果题目明确无重复，可以不写 same，但能主动说明这个扩展会加分。

八、用斜率分组为什么不会漏直线

固定基准点 A 后，任何经过 A 的直线都可以由“斜率”唯一标识：同一条非垂直直线上的点与 A 的 dy/dx 相等；垂直线统一标识为 (1,0)。因此哈希表里每个 key 其实代表一条穿过 A 的直线。

固定 A
        slope=1/1  -> A-B-C 这条线
        slope=0/1  -> A-D   水平线
        slope=1/0  -> A-E   垂直线

外层枚举所有点作为 A，则任意一条最优直线上的点都至少会在某一次枚举中被其中一个点作为基准点统计到。也就是说，算法不会漏掉全局最优直线，只是同一条直线可能被多个基准点重复统计；重复统计不影响取最大值。

九、坐标差和 key 的工程细节

如果坐标范围较大，dx = xj - xi 和 dy = yj - yi 也可能触碰整数边界。Java 中 LeetCode 原题坐标范围通常可放进 int，但工程里可以改用 long 计算差值和 gcd。

key 的构造也要稳定。字符串 "dy/dx" 简单直观，面试足够；追求性能时可以自定义 pair 类并正确实现 equals/hashCode，或把两个归一化整数编码到一个 long。无论哪种方式，关键不是编码形式，而是“同一条斜率必须得到同一个 key，不同斜率不能碰到同一个 key”。

八、常见误区与追问

误区：用 double 作为哈希 key。 浮点精度会导致斜率比较不可靠。
误区：没有约分。 (1,2) 和 (2,4) 会被当成不同斜率。
误区：没有统一符号。 (1,-1) 和 (-1,1) 实际同斜率，却可能分到不同 key。
误区：忘记把基准点加回答案。 哈希表统计的是其他点数量，最终要 best + 1。
追问：垂直线如何表示？ 单独归一成 (1,0)，不要计算除法。
追问：如果存在重复点怎么办？ 对与基准点坐标完全相同的点单独计数，最终加到同斜率数量上。

十、加强记忆

固定一个点，其他点按斜率分组。
斜率用约分后的 (dy, dx)，不要用 double。
垂直线、水平线单独归一化。
每个基准点重新建哈希表，答案是最大斜率频次加基准点。
追问重复点时，用 same 单独处理重合坐标。

简化版

详细版