2013. Detect Squares

naive

At most 3000 calls in total will be made to add and count

把所有點都去試試看 其他三個點是否存在, 超級窮舉, 3000*3000 => 爆炸

using x, y range, 對角線的想法

• 0 <= x, y <= 1000

1. 首先紀錄所有點

2. count() 時, 把 input（point[0], point[1]）當作 x, y 起點

(i, j) 對角線的點, 其他兩點會是...

for i to 1000
x = point[0], y =point[1]
d = abs(i - x)

so 上對角線的點: (i, j)
j = y+d               

i,j     [ x, j]

[i, y]    x,y


下對角線的點: (i, j)
j = y-d               

[i, y]    x,y

i, j      [x, j]

在 x 軸上窮舉 i = 0~1000 : 那距離 d = abs(i-x)

利用這個距離

去算對角線（i, j）（上對角線, 下對角線）, 然後去找是不是有符合的其他兩個點

數量就是這三個點的數量乘積

T: count: O(1000) , add: O(1)
S: O(1000*1000)

class DetectSquares {

    int[][] pCounts;
    public DetectSquares() {
        pCounts = new int[1001][1001];
    }
    
    public void add(int[] point) {
        pCounts[point[0]][point[1]]++;
    }
    
    public int count(int[] point) {
        int x = point[0];
        int y = point[1];
        int res = 0;
        for (int i = 0; i <= 1000; i++) {
            int dist = Math.abs(i - x);
            if (dist == 0) { // if 點重合 pass
                continue;
            }
            
            int j = y + dist;
            if (j >= 0 && j <= 1000) {
                res += pCounts[i][j]*pCounts[x][j]*pCounts[i][y];
            }
            
            j = y - dist;
            if (j >= 0 && j <= 1000) {
                res += pCounts[i][j]*pCounts[x][j]*pCounts[i][y];
            }
        } 
        return res;
    }
}

/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares obj = new DetectSquares();
 * obj.add(point);
 * int param_2 = obj.count(point);
 

for i to 1000
x = point[0], y =point[1]
d = abs(i - x)

so 
j = y+d               

i,j     [ x, j]

[i, y]    x,y


j = y-d               

[i, y]    x,y

i, j      [x, j]

T: count: O(1000) , add: O(1)
S: O(1000*1000)
 */