LeetCode 149：用gcd归一化斜率，O(n²)哈希解共线点问题-开发者社区

最近刷题的时候，我一直在用腾讯元宝网页版里的 DeepSeek 当陪练。说实话，之前我对“用大模型辅助刷算法题”这件事挺保守的，总觉得会变成“抄答案工具”，直到碰到 LeetCode 149 这道题，发现让 AI 讲思路、帮我分析边界条件，效率确实比自己死磕快不少。今天就拿这道题完整拆一遍，题目本身很经典，解法也不算难，但它涉及的几何表示、精度处理、哈希设计这些点，几乎是刷题面试里绕不开的坎。

如果你是正在刷 LeetCode 热门 100 题、准备面试算法轮，或者只是想搞明白“为什么计算斜率不能直接存 double”，这篇文章应该对你有用。我会从最朴素的暴力思路讲起，一步步推到最优的 O(n²) 哈希解法，中间补上数学原理、完整可运行的 Java 和 Python 代码，以及我实际用 DeepSeek 辅助刷题时踩过的坑和问问题的技巧。

1. 题目本身不难，难在“直线”怎么表示

1.1 先复述一下题意

LeetCode 149 的题目描述很短：给你一个二维平面上的点数组points，每个点用[x, y]表示，要你找出“落在同一条直线上最多的点数”。

输入示例是这样的：

输入：points = [[1,1],[2,2],[3,3]] 输出：3

三个点都在同一条直线 y = x 上，所以答案是 3。第二个官方示例是六个点，正确答案是 4，这条直线经过[1,1]、[3,2]、[5,3]、[4,1]这四个点——注意，这四个点不是简单地“i 和 i+1”连在一起，你得自己能判断共线才行。

这题还有一个容易忽略的地方：点可以是重复的。也就是说，输入里可能出现完全相同坐标的点，比如 [[1,1], [1,1], [2,2]]，答案应该是 3，因为任意两个重合的点必然能和另一个点共线。这个特性在实现时特别容易漏，后面我会专门讲。

1.2 最容易想到的暴力思路

先把最简单的做法写出来：枚举任意两个点确定一条直线，再遍历所有点统计有多少点在直线上，取最大值。

判断一个点 P 是否在由点 A、B 确定的直线上，最标准的几何方法是看叉积是否为 0：

(P.x - A.x) * (B.y - A.y) == (P.y - A.y) * (B.x - A.x)

这个式子的含义是向量 AP 和向量 AB 平行，既然是共起点，平行就是在同一条直线上。

三条嵌套循环，时间复杂度 O(n³)。LeetCode 这题的points.length最多是 300，O(n³) 大概是 2700 万次运算，其实也能过，我实测在 Java 里差不多几百毫秒以内。但刷题不能只看过不过，面试官一定会追问优化方案，所以暴力解只能当热身。

1.3 暴力解虽然能过，但隐藏着两个问题

第一个问题是重复计算：三条直线 A-B、A-C、B-C 如果描述的是同一条几何直线，暴力法会分别统计三次，做了大量无用功。第二个问题更重要——叉积判断法本身没有错，但它要求 O(n³) 的复杂度，这在点规模变大时是不可接受的。

所以常规做法是换一个角度：固定一个点作为基准，看其它点相对于它都落在哪些方向上，方向相同的就是共线。这个思路是典型的“降维”：把判断所有点是否共线，转化为统计斜率是否相等。复杂度从 O(n³) 降到 O(n²)，空间换时间。

既然要统计斜率相等，那核心问题就来了：斜率怎么表示才足够精确？

2. 核心数学原理：用坐标差代替斜率，躲开浮点精度坑

2.1 直接存 double 斜率到底行不行

一提“斜率”，很多人第一反应是计算(y2 - y1) / (x2 - x1)，然后存成 double。但这道题藏着两个明显的坑：

当直线垂直时，x2 - x1 = 0，斜率是无穷大，double 表示不了。
double 存在浮点精度误差。比如 (1, 3) 和 (2, 6) 的斜率都是 3.0，但在某些坐标值下，比如 (1, 1) 和 (3, 3)，除以 2 是 1.0；而 (1, 1) 和 (7, 5) 的斜率大约是 0.6666666666666666，另一个接近的点算出来可能是 0.6666666666666667，用 double 做 key 就可能误判。

坐标范围如果比较小，double 通常能蒙对，但 LeetCode 这类题目经常卡边界。更重要的是，用浮点数做 Hash 的 key，本身就是一种不严谨的工程习惯。正确做法是避免浮点，用整数对表示方向。

2.2 用 (dx, dy) 和最大公约数归一化

两个坐标点之间的相对方向，完全可以由坐标差 (dx, dy) 唯一表示。比如从 (1, 1) 到 (3, 3)，坐标差是 (2, 2)；从 (1, 1) 到 (5, 5)，坐标差是 (4, 4)。这两个方向其实是一样的，要合并成同一个 key，就做“归一化”：把 dx 和 dy 同时除以它们的最大公约数（gcd）。

(2, 2) 除以 gcd(2,2)=2 → (1, 1) (4, 4) 除以 gcd(4,4)=4 → (1, 1)

所以 (2,2) 和 (4,4) 都归一化成 (1,1)，它们就匹配上了。同理，(1, 2) 和 (2, 4) 归一化后都是 (1, 2)。

这个做法的本质是：用“最简分数的分子分母”表示斜率方向，而不是用浮点商。在数学上，分数是精确值，没有精度问题。工程上，我们只是拿整数对做字符串或嵌套 Map 的 key，完全可控。

2.3 分子分母的符号统一和特殊方向处理

归一化还有一个容易被忽略的细节：符号要统一，否则会出幺蛾子。

比如从点 A 到点 B 的方向是 (-1, -2)，从点 A 到点 C 的方向是 (1, 2)，这两条线相对于 A 其实是同一个方向（都在同一条直线上）。但如果你不处理符号，(-1, -2) 和 (1, 2) 会被当成两个 key，导致统计错误。

我统一符号的做法是：保证 dx > 0 作为优先条件；如果 dx == 0，则保证 dy > 0。具体来说：

如果 dx < 0，就把 dx 和 dy 同时取反（变成 -dx, -dy）。
如果 dx == 0 且 dy < 0，就把 dy 取反。
垂直线的归一化结果是 (0, 1)，水平线是 (1, 0)，这两个特殊方向天然统一。

这样处理之后，任意一条直线相对于同一个基准点的方向表示是唯一的。

3. 枚举基准点的 O(n²) 解法

3.1 固定一个点，统计其它点相对它的方向

核心思路很直接：每次选定一个点points[i]作为基准点，遍历所有其它点，计算相对坐标差并归一化，然后用哈希表统计每个方向出现了多少次。同一方向出现 k 次，就意味着加上基准点共有 k + 1 个点共线（这里先不考虑重复点，重复点单独算）。

对每个基准点 i，取统计到的最大值；所有 i 的最大值里再取最大，就是全局答案。

复杂度是 O(n²)：外层有 n 个基准点，内层遍历 n-1 个点，每个点做一次 gcd 归一化。gcd 的时间复杂度是 O(logC)，C 是坐标差的最大绝对值，但实际常数非常小，LeetCode 这道题 n ≤ 300，跑起来飞快。

3.2 重复点到底怎么处理

输入里如果有重复坐标，比如 (1,1) 出现三次，那么无论直线怎么选，这三个点都一定共线。处理重复点我见过两种思路：

第一种是预处理，先用哈希表数出每个坐标出现多少次，枚举时按去重后的点算，最后把重复点数乘进去。这个思路通用，但实现起来要维护两个映射，代码偏长。

第二种更简洁：枚举基准点 i 时，统计与 points[i] 完全重合的其它点的数量，记为duplicate；方向统计里的 best 只统计不重合的、与基准点共线的点。那么以 i 为基准点所在的直线上的总点数就是best + duplicate + 1。

这里有个小细节，+1 表示基准点本身。只要想到位了，重复点其实很好处理。

3.3 哈希表的 key 设计：字符串还是嵌套 Map

归一化得到 (dx, dy) 之后，怎么当 key 放进哈希表？我个人推荐用单个字符串，比如dx + "," + dy，代码简单且不容易出错。还有人会用嵌套 Map，Map<Integer, Map<Integer, Integer>>，外层存 dx，内层存 dy，理论上能省字符串拼接的开销，但代码读起来会绕，实测在 n=300 时性能差别可以忽略。

字符串拼接的唯一问题是可能引入分隔符冲突，比如 (11, 2) 拼成 "11,2"，(1, 12) 拼成 "1,12"，这两者不一样，所以其实不会冲突。只要分隔符固定且不是数字，就没问题。

如果更追求效率或者不想用字符串，也可以把 (dx, dy) 编码成一个 long：((long) dx << 32) | (dy & 0xffffffffL)，但这就属于优化彩蛋了，面试时能聊出来是加分项，日常写还是字符串最直观。

4. 能直接跑的 maxPoints 实现（Java + Python）

4.1 Java 版本代码（注释详解）

下面是我最终提交的版本。为了讲解清晰，内层循环从 0 遍历到 n-1，跳过自己。这样每一对点会处理两次，但逻辑直白，最适合理解：

class Solution { public int maxPoints(int[][] points) { int n = points.length; if (n <= 2) { return n; } int ans = 0; for (int i = 0; i < n; i++) { // key 是归一化后的方向，value 是除基准点外该方向上的点数 Map<String, Integer> map = new HashMap<>(); int duplicate = 0; // 与 points[i] 重合的点个数 int best = 0; // 所有方向中，不重合点数的最大值 for (int j = 0; j < n; j++) { if (i == j) { continue; } int dx = points[j][0] - points[i][0]; int dy = points[j][1] - points[i][1]; // 完全重合的点，先单独计数 if (dx == 0 && dy == 0) { duplicate++; continue; } // 统一符号，保证方向表示唯一 if (dx < 0) { dx = -dx; dy = -dy; } else if (dx == 0 && dy < 0) { dy = -dy; } // 用最大公约数归一化 int g = gcd(Math.abs(dx), Math.abs(dy)); dx /= g; dy /= g; String key = dx + "," + dy; int count = map.getOrDefault(key, 0) + 1; map.put(key, count); best = Math.max(best, count); } // best 是“除基准点以外共线的点”，加上基准点本身和重复点 ans = Math.max(ans, best + duplicate + 1); } return ans; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }

有几个点需要额外说明：

我计算的是“方向”而不是“经过基准点的直线的斜率”，因为从同一个基准点出发，方向相同必然共线；方向不同的点不可能和基准点在同一条直线上。
duplicate这组点不参与 map 计数，是因为它们和基准点重合，无论 map 里的方向是哪个，它们都能加进去。最后统一加上去最安全。
一开始if (n <= 2) return n;属于边界保护：一个点或两个点一定在同一直线上，不需要走循环。

4.2 Python 版本参考

如果你主要在 Python 环境刷题，下面是等价写法：

import math from typing import List class Solution: def maxPoints(self, points: List[List[int]]) -> int: n = len(points) if n <= 2: return n ans = 0 for i in range(n): cnt = {} duplicate = 0 best = 0 for j in range(n): if i == j: continue dx = points[j][0] - points[i][0] dy = points[j][1] - points[i][1] if dx == 0 and dy == 0: duplicate += 1 continue if dx < 0: dx, dy = -dx, -dy elif dx == 0 and dy < 0: dy = -dy g = math.gcd(abs(dx), abs(dy)) dx //= g dy //= g key = (dx, dy) cnt[key] = cnt.get(key, 0) + 1 best = max(best, cnt[key]) ans = max(ans, best + duplicate + 1) return ans

Python 版本里我直接用元组(dx, dy)当 key，比字符串更省事，这也是 Python 哈希的天然优势。

4.3 复杂度分析

时间复杂度：外层循环 n 次，内层循环 n 次，每次做一次 gcd，所以是 O(n² logC)。C 表示坐标差的绝对值上限，LeetCode 这题坐标范围是 [-10^4, 10^4]，gcd 的常数非常小。如果不强调 log 因子，直接说 O(n²) 也没问题。

空间复杂度：每个基准点 i 都要开一个哈希表，最坏情况下表里有 n 个不同的方向，所以是 O(n)。

对比前面的 O(n³) 暴力法，这个优化是数量级上的提升。n=300 时，O(n³) 大概是 2700 万次运算，O(n²) 是 9 万次运算，差距接近 300 倍，放到更大的数据范围上根本不是一个量级。

5. 用腾讯元宝 + DeepSeek 辅助刷题的实际体验

5.1 我是怎么提问的：让 AI 当陪练而不是直接要答案

回到开头说的事。我刷这道题的时候，第一版暴力解法写完能过，但总觉得不够优雅。于是我打开腾讯元宝网页版，切换到 DeepSeek，问了一个很具体的问题：

“LeetCode 149，我目前用 O(n³) 枚举三点叉积判断共线，想优化到 O(n²)，但不想直接用 double 存斜率，有什么思路？”

注意，我刻意没有说“给我代码”，而是交代了我当前的思路和约束条件。这样提问的好处是，大模型不会直接甩一段代码让你抄，而是会围绕“固定基准点 + gcd 归一化”这个方向展开讲解。结果 DeepSeek 给了两条核心提示：一是用 (dx, dy) 归一化代替斜率，二是单独处理重复点。这两个点正是这道题 80% 的坑所在。

我后来还追问了一句“为什么这里不能用 double”，它的解释基本靠谱：浮点数在极端坐标下会产生相同方向不同 key 的问题，而且用浮点当哈希 key 不够严谨。虽然细节没有我上面写的这么全，但已经能帮我建立正确的思考框架了。

5.2 大模型在这道题上容易犯的错

AI 不是万能的，尤其在代码细节上。我试验了几种不同的提问方式，发现 DeepSeek 在这道题上偶尔会犯一个典型错误：漏掉重复点处理。如果你直接问“给我最优解法”，它给出的代码很可能只处理了 dx=0 的垂直线，却忘了对 dx=0 && dy=0 时重复点的特判。

还有一种情况是符号不统一，生成的代码里没有处理 dx < 0 的情况，导致 (-1, 1) 和 (1, -1) 被算成两个方向，结果答案偏小。

所以我的经验是：AI 给出的代码，一定要自己手动构造几个边界用例去验。比如：

[[0,0],[1,1],[0,0]] // 重复点，期望 3 [[0,0],[1,1],[-1,-1]] // 负坐标方向，期望 3 [[0,0],[0,1],[0,2]] // 垂直线，期望 3 [[0,0],[1,0],[2,0]] // 水平线，期望 3

把这些用例喂给 DeepSeek，让它自己跑一遍逻辑，或者喂给它报错信息，它会纠正得很快。这是把 AI 当“结对编程伙伴”而不是“答案生成器”的正确姿势。

5.3 本地部署和工具链接入的边界

最近“DeepSeek 本地部署”、“vscode 接入 DeepSeek”、“codex 接入 DeepSeek”这些话题很火，我也试过本地跑小参数模型，结论很直接：小参数本地模型做代码补全和简单问答还行，但像 149 这种需要多轮推理的题目，理解能力和回答质量跟在线大模型差距挺明显。

如果你真的想在刷题工作流里接入 DeepSeek，我更推荐用网页版或者 API 的方式，而不是纠结本地部署。日常罪恶感最少的方式是：在 vscode 里装一个支持自定义模型的插件，把 DeepSeek API 配进去，让它帮你补注释、解释报错、生成测试用例。核心思路还是自己先想清楚再问，这样 AI 才能真正帮你提效。

6. 常见问题与避坑指南

6.1 边界条件检查清单

这类几何题最容易挂在边界上。我在提交前一定会检查这几项：

n = 0 或 n = 1：直接返回 n。
所有点都相同：像 [[1,1],[1,1],[1,1]]，答案应为 3。
只有两个点：不管坐标是否相同，答案都应该是 2（n=2 时直接返回）。
所有点都在一条垂直/水平线上：垂直线归一化成 (0, 1)，水平线归一化成 (1, 0)，不能因为分母为 0 而出错。
负坐标下方向符号是否统一：(-1, -2) 和 (1, 2) 应该对应同一个 key。
坐标差非常大的时候 gcd 是否能算对：注意 gcd 要用绝对值，否则可能计算出负数导致死循环。

我一般会写一个非常小的测试函数批量验证这些样例，确保边界全过再提交。

6.2 关于性能实测与参数选择

我第一次用暴力叉积法提交，内存大概 45 MB，耗时 300 多毫秒。优化成 O(n²) 哈希法之后，内存降到 40 MB 左右，耗时只有 4 毫秒左右。两者都能过这道题，因为 n ≤ 300。

但性能不是唯一的衡量标准。我实际写代码时倾向于选择可读性最好的方案，也就是用字符串 key，而不是用嵌套 Map 或者 long 编码。原因很简单：算法面试里面试官更看重思路表达，而不是 map 的常数优化。如果面试官追问性能优化点，你再抛出 long 编码或者排序方向的思路，能体现深度。

6.3 一题多解：叉积法、double 斜率法、分数归一化怎么选

我把三种常见解法做个对比，方便你根据场景选择：

解法	时间复杂度	优点	缺点	适用场景
暴力叉积	O(n³)	思路最直接，无精度问题	重复计算多，性能差	快速验证、理清题意
double 斜率	O(n²)	代码最简洁	垂直直线难处理，有浮点精度风险	坐标范围小且可控
(dx, dy) + gcd 归一化	O(n²)	精确、无浮点、面试加分	代码稍长，需要处理符号	推荐的标准答案