题目描述

在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示一个点。

请你来判断，这些点是否在该坐标系中属于同一条直线上。

样例

输入：coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
输出：true

输入：coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
输出：false

限制

• 2 <= coordinates.length <= 1000
• coordinates[i].length == 2
• -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
• coordinates 中不含重复的点。

算法

(暴力枚举) $O(n)$

1. 通过做差求出前两个点的向量 (x, y)。
2. 从第三个点开始，我们看每个点与第一个点做差后的向量是否和 (x, y) 平行。这里可以通过乘法判断，防止除法出现的精度和整数被 0 除的问题。

时间复杂度

• 仅遍历一遍数组，故时间复杂度为 $O(n)$。

空间复杂度

• 只需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int n = coordinates.size();
        int x = coordinates[1][0] - coordinates[0][0];
        int y = coordinates[1][1] - coordinates[0][1];

        for (int i = 2; i < n; i++)
            if ((coordinates[i][0] - coordinates[0][0]) * y 
                != (coordinates[i][1] - coordinates[0][1]) * x)
                return false;

        return true;
    }
};