LeetCode 中等难度题目「149. 直线上最多的点数」这道题核心考察对“直线斜率”的理解和哈希表的运用看似简单但细节超多一不小心就会踩坑。下面结合完整代码一步步讲透解题逻辑新手也能轻松看懂。题目回顾题目很直白给你一个数组 points 其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。举个例子如果 points [[1,1],[2,2],[3,3]]那么这三个点在同一条直线上答案就是 3如果 points [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]答案则是 4有4个点共线。核心难点如何表示“同一条直线”如何避免重复计数如何处理斜率的精度问题解题核心思路直线的核心特征是「斜率」—— 同一平面内两点确定一条直线而斜率相同且经过同一点的点必然在同一条直线上。基于这个原理我们可以用「固定一点遍历其他点」的思路具体步骤如下边界处理如果点的数量 ≤ 2直接返回点的数量因为两点必然共线遍历每个点 points[i]将其作为「基准点」计算基准点与其他所有点 points[j]j i的斜率用哈希表记录「斜率对应的点的数量」统计当前基准点对应的最大共线点数更新全局最大值优化剪枝如果当前全局最大值已经 ≥ 剩余未遍历的点的数量或者超过总点数的一半直接终止循环无需继续计算因为不可能出现更大值。关键细节斜率的表示避坑重点这道题最容易踩坑的地方就是「斜率的表示」。直接用 dy/dx 即两点纵坐标差除以横坐标差会有两个问题精度问题浮点数计算会有误差比如 1/3 和 2/6 本是同一个斜率但浮点数表示可能不同特殊情况垂直直线dx0斜率不存在、水平直线dy0斜率为0无法用常规除法表示。解决方案用「最简整数比」表示斜率将 dy 和 dx 化简为互质的整数再用一个唯一的key表示这个比值。具体做法对应代码中的gcd函数和key计算计算两点的横坐标差 dx x_i - x_j纵坐标差 dy y_i - y_j特殊处理dx0垂直直线令 dy1统一表示所有垂直直线的斜率dy0水平直线令 dx1统一表示所有水平直线的斜率符号统一如果 dy 为负将 dx 和 dy 同时取反保证斜率的符号一致比如 2/-3 和 -2/3 是同一个斜率统一为 2/3化简用最大公约数gcd将 dx 和 dy 化简为互质的整数比如 dx4dy2化简为 dx2dy1生成key将二维的 (dy, dx) 转化为一维key避免哈希表的key冲突。代码中用「dy dx * 20001」因为题目中坐标的范围是 [-10^4, 10^4]dx的最大绝对值是 20000乘以20001后再加上dy范围 [-20000, 20000]可以保证每个 (dy, dx) 对应唯一的key。完整代码逐行解析先贴完整代码TypeScript版本再逐行拆解核心逻辑functionmaxPoints(points:number[][]):number{constnpoints.length;if(n2)returnn;// 边界处理2个及以下点必共线letres0;// 最大公约数函数用于化简dx和dyconstgcd(a:number,b:number):number{returnb!0?gcd(b,a%b):a;}// 遍历每个点作为基准点ifor(leti0;in;i){// 剪枝如果当前最大结果已经≥剩余点数量或超过总点数的一半无需继续if(resn-i||resn/2){break;}constmapnewMap();// 记录当前基准点下斜率对应的点的数量// 遍历所有在i之后的点j避免重复计算因为i和j与j和i的斜率相同for(letji1;jn;j){letdxpoints[i][0]-points[j][0];letdypoints[i][1]-points[j][1];// 特殊处理垂直/水平直线统一斜率表示if(dx0){dy1;// 垂直直线斜率统一用(1,0)表示}elseif(dy0){dx1;// 水平直线斜率统一用(0,1)表示}else{// 符号统一dy为负时dx和dy同时取反if(dy0){dx-dx;dy-dy;}// 化简dx和dy为互质整数constgcdXYgcd(Math.abs(dx),Math.abs(dy));dx/gcdXY;dy/gcdXY;}// 生成唯一key存入哈希表constkeydydx*20001;map.set(key,(map.get(key)||0)1);}// 统计当前基准点下最多的共线点数map的值是“与基准点共线的点的数量”需1包含基准点本身letmaxn0;for(constnumofmap.values()){maxnMath.max(maxn,num1);}// 更新全局最大值resMath.max(res,maxn);}returnres;};逐行解析核心代码边界处理if (n 2) return n;—— 这是最基础的优化因为1个点返回12个点返回2都无需后续计算。gcd函数求两个数的最大公约数用于化简dx和dy。比如gcd(4,2)2gcd(3,5)1核心是递归实现“辗转相除法”。外层循环基准点遍历for (let i 0; i n; i)每个i作为基准点后续只遍历j i的点避免重复计算比如i0、j1和i1、j0是同一个斜率无需重复统计。剪枝逻辑if (res n - i || res n / 2) break;—— 比如总共有5个点当前res3剩余未遍历的点只有2个n-i5-32不可能超过3直接终止循环另外最多共线点数不可能超过总点数的一半如果超过早就在之前的基准点中统计到了这一步能大幅提升效率。哈希表mapkey是斜率的唯一标识value是“与基准点i共线且在i之后的点的数量”。内层循环计算斜率for (let j i 1; j n; j)计算基准点i和点j的dx和dy然后进行化简和符号统一生成key存入map。统计当前基准点的最大共线点数num 1是因为map的value是“除基准点外的共线点数”加上基准点本身才是总共线点数。更新全局最大值res每次遍历完一个基准点就用当前的maxn更新res最终res就是答案。常见坑点优化建议坑点1斜率精度问题千万不要用 dy/dx 计算斜率比如用浮点数存储会出现精度误差。比如 dx1、dy3 和 dx2、dy6斜率都是1/3但浮点数表示可能有微小差异导致哈希表认为是两个不同的斜率。坑点2符号不统一比如 dx2、dy-3 和 dx-2、dy3其实是同一个斜率但如果不统一符号会生成两个不同的key。所以代码中才会判断“如果dy0dx和dy同时取反”保证斜率符号一致。坑点3重复计算如果内层循环遍历所有jj从0到n-1j≠i会导致i和j、j和i重复计算浪费时间。所以内层循环只遍历j i的点既避免重复又提升效率。优化建议剪枝逻辑一定要加尤其是当n较大时比如n1000剪枝能大幅减少循环次数避免超时。另外哈希表的key生成方式可以灵活调整只要能保证“不同斜率对应不同key相同斜率对应相同key”即可代码中的「dy dx * 20001」是结合题目坐标范围的最优选择。测试用例验证我们用两个典型测试用例验证代码测试用例1points [[1,1],[2,2],[3,3]]i0基准点[1,1]j1dx-1dy-1 → 符号统一后dx1dy1 → key11*2000120002map{20002:1}j2dx-2dy-2 → 化简后dx1dy1 → key20002map{20002:2}maxn213res3后续循环剪枝最终返回3。测试用例2points [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]i0基准点[1,1]遍历j1~5计算各个斜率最终map中最大value为3对应4个点共线maxn4res4后续循环无法超过4最终返回4。总结这道题的核心是「用最简整数比表示斜率」避免精度和符号问题再通过「固定基准点哈希表计数」的思路统计每个基准点对应的最大共线点数最后结合剪枝优化提升效率。整体难度中等重点在于细节处理——斜率的化简、符号统一、key的生成这些都是避坑的关键。理解之后会发现这道题本质是“哈希表的应用直线斜率的数学理解”掌握后可以举一反三应对类似的几何计数问题。