> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/math/square/2013.-detect-squares.md).

# 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)
```

```java
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)
 */
```