2013. Detect Squares

Medium

Description

設計一個資料結構，支援兩個操作：add(point) 加入一個點，count(point) 計算與給定點能組成軸對齊正方形的方式數。正方形的邊必須平行於 x 軸和 y 軸，且面積大於 0。

Example:

Input: [“DetectSquares”,“add”,“add”,“add”,“count”] Output: [[],[],[],[],[1]] (加入 [3,10],[11,2],[3,2] 後，count([11,10]) 回傳 1)

Intuition#

核心思路：固定查詢點和一個對角點，用邊長推算另外兩個角的位置，查 Hash Map 確認是否存在。

軸對齊正方形由對角線上的兩個點可以唯一確定另外兩個點
給定查詢點 (px, py)，枚舉所有與它 x 座標相同的點 (px, qy) 作為同一邊
邊長 side = |py - qy|，另外兩個角在 (px + side, py) 和 (px + side, qy) 或 (px - side, py) 和 (px - side, qy)

Approaches#

1: 暴力枚舉所有點對#

概念: 對每個查詢，枚舉所有已加入的點對，檢查能否與查詢點構成正方形
時間複雜度: add O(1)，count O(n^2) - n 為已加入的點數
空間複雜度: O(n)

class DetectSquares() {
    private val points = mutableListOf<IntArray>()

    fun add(point: IntArray) {
        points.add(point)
    }

    fun count(point: IntArray): Int {
        val (px, py) = point
        var count = 0
        for (p1 in points) {
            for (p2 in points) {
                if (p1[0] == px && p2[1] == py &&
                    Math.abs(p1[1] - py) == Math.abs(p2[0] - px) &&
                    p1[1] != py && p2[0] != px &&
                    p1[1] == p2[1] && Math.abs(p2[0] - px) > 0) {
                    // 不好寫也容易錯，見下方最佳解
                }
            }
        }
        return count
    }
}

⭐2: Hash Map + 枚舉對角點#

概念: 用 Hash Map 記錄每個座標出現的次數。枚舉所有與查詢點 y 座標不同的已知點作為對角點，計算另外兩個角是否存在
時間複雜度: add O(1)，count O(n) - n 為不重複的點數
空間複雜度: O(n)

class DetectSquares() {
    private val pointCount = HashMap<Long, Int>()
    private val pointsByX = HashMap<Int, MutableList<IntArray>>()

    private fun encode(x: Int, y: Int): Long = x.toLong() * 100001 + y

    fun add(point: IntArray) {
        val key = encode(point[0], point[1])
        pointCount[key] = pointCount.getOrDefault(key, 0) + 1
        pointsByX.getOrPut(point[0]) { mutableListOf() }.add(point)
    }

    fun count(point: IntArray): Int {
        val (px, py) = point
        var result = 0
        // 枚舉與 px 相同 x 座標的點，作為正方形的同一條垂直邊
        val sameX = pointsByX[px] ?: return 0
        for (p in sameX) {
            val qy = p[1]
            if (qy == py) continue // 邊長不能為 0
            val side = qy - py
            // 正方形的另外兩個角
            val c1 = pointCount.getOrDefault(encode(px + side, py), 0)
            val c2 = pointCount.getOrDefault(encode(px + side, qy), 0)
            result += c1 * c2
            val c3 = pointCount.getOrDefault(encode(px - side, py), 0)
            val c4 = pointCount.getOrDefault(encode(px - side, qy), 0)
            result += c3 * c4
        }
        return result
    }
}

注意重複點的處理：同一個座標可以被加入多次，因此用 count 來計數，結果要乘上各角的出現次數。

補充：另一種枚舉策略

也可以枚舉對角點（x, y 都不同於查詢點且構成正方形），但需要確保 |dx| == |dy|：

class DetectSquares() {
    private val countMap = HashMap<Long, Int>()
    private val allPoints = mutableListOf<IntArray>()

    private fun encode(x: Int, y: Int): Long = x.toLong() * 100001 + y

    fun add(point: IntArray) {
        val key = encode(point[0], point[1])
        countMap[key] = countMap.getOrDefault(key, 0) + 1
        allPoints.add(point)
    }

    fun count(point: IntArray): Int {
        val (px, py) = point
        var result = 0
        for (p in allPoints) {
            val (x, y) = p
            // 對角點必須 x != px, y != py, 且 |dx| == |dy|
            if (Math.abs(x - px) != Math.abs(y - py) || x == px || y == py) continue
            result += countMap.getOrDefault(encode(x, py), 0) *
                      countMap.getOrDefault(encode(px, y), 0)
        }
        return result
    }
}

這種方法每次 count 遍歷所有已加入的點（含重複），但避免了重複計數的問題。

🔑 Takeaways#

Pattern: 幾何題用 Hash Map 儲存點的出現次數，枚舉部分頂點推導其餘頂點
關鍵技巧: 軸對齊正方形的性質——固定一條邊就能推出整個正方形；座標編碼成單一 key 方便查找