LeetCode 2013中等数学 & 几何
检测正方形 图解题解
这道题到底在问什么
动态加入点，查询和给定点组成轴对齐正方形的数量。
- 示例
- add([3,10]), add([11,2]), add([11,10]), count([3,2]) → 1
先想最直接的笨办法
枚举所有三点组合太慢。（动画第 3 步）
最优解：一步一步想明白
- 3枚举所有三点组合太慢。
- 4把点计数存起来；查询时枚举对角点，另外两个角由坐标直接确定。
- 5count([3,2])：把查询点当正方形的一个角，枚举「对角点」，看能凑出多少个轴对齐正方形。
- 6遍历已加入的点当对角点：(3,10) Δx=0 同列跳过；(11,2) Δx≠Δy 跳过；(11,10) Δx=8==Δy=8 且非 0 → 合法对角点。
- 7对角点 (11,10) 一确定，正方形另外两角就是 (对角x,查询y)=(11,2) 和 (查询x,对角y)=(3,10)。
- 8对角点 + 两邻角都在 map 里 → 这种正方形的个数 ＝ 三点出现次数的乘积 ＝ 1×1×1 ＝ 1。
- 9对每个合法对角点的乘积求和。本例只有 (11,10) 一个合法对角 → 总数 ＝ 1。
- 12一句话记住：把点计数存起来；查询时枚举对角点，另外两个角由坐标直接确定。
- 15① Δx==Δy 保证四边等长(轴对齐正方形)，≠0 排除退化(同点/同线)。② 用乘积是因为同一坐标可能被 add 多次，每个角各有出现次数，组合数 = 三者相乘。枚举对角点天然覆盖四个方向，不会重复也不会漏。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=math 连刷同类题；卡住时用 AI 答疑问“为什么枚举对角点就够”。
⚠️ 容易写错的地方
✗ 错：枚举对角点时漏判 Δx ≠ 0
✓ 对：必须 |Δx|==|Δy| 且 ≠ 0
Δx=0 是同列(退化成线)、同点距离0，都不是正方形；要严格相等的非零边长。
✗ 错：用列表存点、count 时去重
✓ 对：用 Counter 计数，乘积统计重复点
同一坐标可能 add 多次，每个角的出现次数都要计入乘积。
✗ 错：枚举正方形的边(两两配对) O(n²)
✓ 对：枚举对角点 O(n)，另两角直接算出
对角点一定后正方形唯一确定，O(n) 即可，比枚举边对快。
完整代码（Python / C++ / Java）
Python
class DetectSquares:
def __init__(self):
from collections import Counter
self.points = Counter()
def add(self, point):
self.points[tuple(point)] += 1
def count(self, point):
x, y = point
ans = 0
for (px, py), cnt in self.points.items():
if px == x or abs(px - x) != abs(py - y): # 同列跳过 + 等边长
continue
ans += cnt * self.points[(x, py)] * self.points[(px, y)]
return ansC++
class DetectSquares {
map<pair<int,int>, int> cnt;
int get(int x, int y) { // 不存在返回 0，且不插入
auto it = cnt.find({x, y});
return it == cnt.end() ? 0 : it->second;
}
public:
void add(vector<int> point) {
cnt[{point[0], point[1]}]++;
}
int count(vector<int> point) {
int x = point[0], y = point[1], ans = 0;
for (auto& [p, c] : cnt) {
int px = p.first, py = p.second;
if (px == x || abs(px - x) != abs(py - y)) continue; // 同列跳过 + 等边长
ans += c * get(x, py) * get(px, y); // 用 get 避免迭代中插入
}
return ans;
}
};Java
class DetectSquares {
Map<String, Integer> cnt = new HashMap<>();
public void add(int[] point) {
String key = point[0] + "," + point[1];
cnt.put(key, cnt.getOrDefault(key, 0) + 1);
}
public int count(int[] point) {
int x = point[0], y = point[1], ans = 0;
for (String key : cnt.keySet()) {
String[] parts = key.split(",");
int px = Integer.parseInt(parts[0]), py = Integer.parseInt(parts[1]);
if (px == x || Math.abs(px - x) != Math.abs(py - y)) continue; // 同列跳过 + 等边长
ans += cnt.get(key) * cnt.getOrDefault(x + "," + py, 0) * cnt.getOrDefault(px + "," + y, 0);
}
return ans;
}
}套路模板 · 枚举对角点骨架
# 检测正方形（枚举对角点）骨架
points = Counter()
def add(p): points[tuple(p)] += 1
def count(x, y):
ans = 0
for (px, py), c in points.items(): # 枚举对角点
if abs(px-x) != abs(py-y) or px == x: continue # 等边长且非退化
ans += c * points[(px, y)] * points[(x, py)] # 另两角乘积
return ans复杂度
时间复杂度
add O(1) / count O(n)
add 计数 O(1)；count 遍历所有不同点找对角
空间复杂度
O(n)
Counter 存所有加入过的点
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 检测正方形 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
整体思路是什么？+
用 Counter 记每个坐标出现次数。add 直接 +1。count(x,y)：遍历所有已存点当「对角点」(px,py)，若 |px−x|==|py−y| 且 ≠0，则另两角是 (px,y) 和 (x,py)，把 cnt(px,py)×cnt(px,y)×cnt(x,py) 累加进答案。
这道题为什么用「几何」，换最直接的暴力解会差在哪？+
几何抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。