給定
rectangles陣列，每個元素[width, height]代表一個矩形。若兩個矩形的寬高比相同（w1/h1 == w2/h2），則稱為可互換。回傳可互換矩形的配對數。
Example:
Input: rectangles = [[4,8],[3,6],[10,20],[15,30]] Output: 6 （所有矩形的寬高比都是 1
，C(4,2) = 6）
Intuition
TIP
核心思路：將每個矩形的寬高比用最簡分數表示（除以 GCD），然後用 HashMap 統計相同比例的數量，再計算組合數 C(n,2)。
- 直接用浮點數比較可能有精度問題，改用最簡分數
(w/gcd, h/gcd)作為 key - 對每組相同比例的
count個矩形，配對數為count * (count - 1) / 2 - 或者邊遍歷邊累加：新加入一個矩形時，它能與之前所有相同比例的矩形配對
Approaches
1. HashMap + GCD (Two Pass) — O(n log(max(w,h))) / O(n)
- Idea: 先統計每個最簡分數的出現次數，再對每組計算 C(n,2)
- Time:
O(n log(max(w,h)))- GCD 計算為 O(log) - Space:
O(n)- HashMap 儲存
class Solution {
fun interchangeableRectangles(rectangles: Array<IntArray>): Long {
val map = HashMap<Long, Long>()
for ((w, h) in rectangles) {
val g = gcd(w, h)
// 用一個 Long 編碼最簡分數，避免用 Pair
val key = (w / g).toLong() * 100_001 + (h / g).toLong()
map[key] = (map[key] ?: 0L) + 1L
}
var pairs = 0L
for (count in map.values) {
pairs += count * (count - 1) / 2
}
return pairs
}
private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}⭐ 2. HashMap + GCD (One Pass) — O(n log(max(w,h))) / O(n)
- Idea: 邊遍歷邊累加配對數：加入新矩形時，它與 map 中已有的相同比例矩形都能配對
- Time:
O(n log(max(w,h)))- GCD 計算 - Space:
O(n)- HashMap 儲存
class Solution {
fun interchangeableRectangles(rectangles: Array<IntArray>): Long {
val map = HashMap<Long, Long>()
var pairs = 0L
for ((w, h) in rectangles) {
val g = gcd(w, h)
val key = (w / g).toLong() * 100_001 + (h / g).toLong()
val count = map.getOrDefault(key, 0L)
pairs += count
map[key] = count + 1
}
return pairs
}
private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}WARNING
避免使用浮點數 width.toDouble() / height 作為 HashMap key，因為浮點數精度問題可能導致相同比例被判為不同。用 GCD 化簡為最簡分數是安全的做法。
🔑 Takeaways
- Pattern: 分組配對計數 -> HashMap 統計 + C(n,2) 或 One-Pass 累加
- Key trick: 比例問題用 GCD 最簡分數取代浮點數比較；配對數的 One-Pass 累加避免二次遍歷