1037. 有效的回旋镖【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 叉积判不共线

1. 📝 题目描述

• leetcode

给定一个数组 points，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，如果这些点构成一个回旋镖则返回 true。

回旋镖定义为一组三个点，这些点各不相同且不在一条直线上。

---

示例 1：

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

---

示例 2：

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

---

提示：

• points.length == 3
• points[i].length == 2
• 0 <= xi, yi <= 100

2. 🎯 s.1 - 叉积判不共线

js

/**
 * @param {number[][]} points
 * @return {boolean}
 */
var isBoomerang = function (points) {
  const [x1, y1] = points[0]
  const [x2, y2] = points[1]
  const [x3, y3] = points[2]

  // 检查三点是否共线
  // 判断斜率是否相等，避免除法
  return (y2 - y1) * (x3 - x2) !== (y3 - y2) * (x2 - x1)
}

• 时间复杂度：$O(1)$，只需要进行常数次的计算
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间

算法思路：

• 三点不共线即构成回旋镖，共线则斜率相等：$\frac{y_2-y_1}{x_2-x_1}=\frac{y_3-y_2}{x_3-x_2}$
• 通过交叉相乘避免除法：$(y_2-y_1)\times (x_3-x_2)\ne (y_3-y_2)\times (x_2-x_1)$