一、题目描述
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
代码语言：javascript复制示例 1：
输入：points = [[1,1],[2,2],[3,3]]
输出：3
示例 2：
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4
提示：
1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
points 中的所有点 互不相同二、解题思路
我们知道，两个点可以确定一条线。
因此一个朴素的做法是先枚举两条点（确定一条线），然后检查其余点是否落在该线中。
为了避免除法精度问题，当我们枚举两个点 i 和 j 时，不直接计算其对应直线的 斜率和 截距，而是通过判断 i 和 j 与第三个点 k 形成的两条直线斜率是否相等（斜率相等的两条直线要么平行，要么重合，平行需要 4 个点来唯一确定，我们只有 3 个点，所以可以直接判定两直线重合）。
已知三点A(x0,y0) B(x1,y1) C(x2,y2)，AB和BC斜率相等可得
(y1-y0)/(x1-x0)=(y2-y1)/(x2-x1)
则(y1-y0)*(x2-x1)=(y2-y1)*(x1-x0)
三、代码
代码语言：javascript复制public class Solution {
public int maxPoints(int[][] points) {
int n = points.length;
int ans = 1;
for (int i = 0; i < n; i ) {
int[] x = points[i];
for (int j = i 1; j < n; j ) {
int[] y = points[j];
int cnt = 2;
for (int k = j 1; k < n; k ) {
int[] p = points[k];
int s1 = (y[1] - x[1]) * (p[0] - y[0]);
int s2 = (p[1] - y[1]) * (y[0] - x[0]);
if (s1 == s2) cnt ;
}
ans = Math.max(ans, cnt);
}
}
return ans;
}
public static void main(String[] args) {
Solution solution=new Solution();
int[][] points={{1,1},{2,2},{3,3}};
System.out.println(solution.maxPoints(points));
}
}四、复杂度分析
时间复杂度：O(n^3) 空间复杂度：O(1)
