給定一組二維平面上的點
points，找出最多有多少個點在同一條直線上。
Example:
Input: points = [[1,1],[2,2],[3,3]] Output: 3
Intuition
TIP
核心思路：固定一個點，用斜率分組其他點，找出同斜率最多的點數。
- 兩點確定一條直線，三個以上的點共線意味著任兩點間的斜率相同
- 固定一個點 i，計算它與其他所有點的斜率，用 HashMap 計數
- 斜率用分數（約分後的 dy/dx）表示，避免浮點數精度問題
- 需要特別處理垂直線（dx=0）和水平線（dy=0）
Approaches
1. Brute Force: Triple Loop — O(n^3) / O(1)
- Idea: 枚舉所有三點組合，檢查是否共線
- Time:
O(n^3)- 三重迴圈 - Space:
O(1)
class Solution {
fun maxPoints(points: Array<IntArray>): Int {
val n = points.size
if (n <= 2) return n
var result = 2
for (i in 0 until n) {
for (j in i + 1 until n) {
var count = 2
for (k in j + 1 until n) {
// 用叉積判斷共線：(y2-y1)(x3-x1) == (y3-y1)(x2-x1)
val cross = (points[j][1] - points[i][1]).toLong() *
(points[k][0] - points[i][0]) -
(points[k][1] - points[i][1]).toLong() *
(points[j][0] - points[i][0])
if (cross == 0L) count++
}
result = maxOf(result, count)
}
}
return result
}
}⭐ 2. HashMap Slope Grouping — O(n^2) / O(n)
- Idea: 固定每個點，用約分後的斜率作為 key 分組，找出最大共線數
- Time:
O(n^2)- 兩層迴圈 - Space:
O(n)- HashMap
class Solution {
fun maxPoints(points: Array<IntArray>): Int {
val n = points.size
if (n <= 2) return n
var result = 2
for (i in 0 until n) {
val slopeMap = HashMap<String, Int>()
for (j in i + 1 until n) {
var dy = points[j][1] - points[i][1]
var dx = points[j][0] - points[i][0]
// 約分
val g = gcd(Math.abs(dy), Math.abs(dx))
if (g != 0) {
dy /= g
dx /= g
}
// 統一符號：讓 dx 為正，或 dx=0 時讓 dy 為正
if (dx < 0) {
dx = -dx
dy = -dy
} else if (dx == 0) {
dy = Math.abs(dy)
}
val key = "$dy/$dx"
slopeMap[key] = (slopeMap[key] ?: 0) + 1
}
for (count in slopeMap.values) {
result = maxOf(result, count + 1) // +1 包含點 i 自己
}
}
return result
}
private fun gcd(a: Int, b: Int): Int {
return if (b == 0) a else gcd(b, a % b)
}
}🔑 Takeaways
- Pattern: 固定一個元素 + HashMap 分組是處理「共性」問題的常見手法
- Key trick: 用約分後的分數表示斜率避免浮點精度問題；用叉積判斷共線也是常用替代方案