解題說明
Right Triangles
題目描述：給定一個 m×n 的二維矩陣 grid，其中元素為 0 或 1。計算由三個值為 1 的格子組成的直角三角形數量，其中直角頂點與另外兩個頂點分別同行和同列。
解題思路：對於每個值為 1 的格子 (i, j)，它可以作為直角頂點。設該行中 1 的數量為 rowCount[i]，該列中 1 的數量為 colCount[j]。以 (i, j) 為直角頂點的三角形數量為 (rowCount[i] - 1) × (colCount[j] - 1)，因為需從同行選一個（排除自身）和從同列選一個（排除自身）。將所有格子的結果加總即可。
C++ 解法
複雜度分析
時間複雜度：O(m × n) — 兩次遍歷矩陣，每次 O(m × n)。
空間複雜度：O(m + n) — 儲存每行和每列的 1 的數量。
虛擬碼
1. Count number of 1s in each row -> rowCount[] 2. Count number of 1s in each column -> colCount[] 3. For each cell (i, j) where grid[i][j] == 1: a. Add (rowCount[i] - 1) * (colCount[j] - 1) to answer 4. Return answer
其他解法
暴力枚舉三個點 O(m³ × n³)：枚舉所有三個 1 格子的組合並檢查是否形成直角三角形。時間複雜度極高，不實用。
按行分組 + 列計數 O(m × n)：本質上與上述方法相同，但先按行列分組再用組合數計算，程式碼結構不同但效率一致。
延伸思考
- 如果要計算的是等腰直角三角形（兩直角邊等長），該如何修改？
- 如果格子值不限於 0/1 而是任意正整數，且要求三個格子值的乘積最大，問題如何變化？
- 如何將此方法擴展到三維空間中的直角三角形計數？