1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class DetectSquares {
Map<String, Integer> pointCount;
public DetectSquares() {
pointCount = new HashMap<>();
}
public void add(int[] point) {
String currPoint = point[0] + "," + point[1];
pointCount.put(currPoint, pointCount.getOrDefault(currPoint, 0) + 1);
}
public int count(int[] point) {
int count = 0;
for (Map.Entry<String, Integer> entry : pointCount.entrySet()) {
String[] currPoint = entry.getKey().split(",");
int x = Integer.parseInt(currPoint[0]), y = Integer.parseInt(currPoint[1]);
if (x == point[0] || y == point[1] || Math.abs(point[0] - x) != Math.abs(point[1] - y)) {
continue;
}
String targetOne = x + "," + point[1];
String targetTwo = point[0] + "," + y;
count += (pointCount.getOrDefault(targetOne, 0) * pointCount.getOrDefault(targetTwo, 0) * entry.getValue());
}
return count;
}
}
|
穷举. 让每个add进来的point做对角线. 因为假设传进来一个point, 我们要看它能和有的点哪些组成squares. 那么肯定有point做对角线那个. 于是我们让所有点都做对角线, 然后看每个点做对角线的时候, 能产生出多少种squares. 这就是答案. 还得是穷举.
需要注意的是我们构建的是正方形, 因此第18行最后一个条件很重要.
时间复杂度: O(n)
空间复杂度: O(n)
