检测正方形 图解题解
这道题到底在问什么
- 输入
- add(1,1); add(1,4); add(4,1); add(4,4); count(1,1)
- 输出
- 1（这四个点正好围成一个边长 3 的正方形）
最优解：一步一步想明白
- 3核心：先锁一条竖边定出边长，正方形剩下两个角就唯一确定，去集合里查它们在不在、各有几个。
- 4数据结构就一个计数哈希表 cnt；难点全在 count 里怎么由一条竖边推出另两个角。
- 5一开始集合是空的，平面上灰色的位置是接下来要加入的点，先认认它们的坐标。
- 6add (1,1)：把点 (1,1) 加进集合，它的次数记为 1（绿色就是刚加入的这个点）。
- 7add (1,4)：把点 (1,4) 加进集合，它的次数记为 1（绿色就是刚加入的这个点）。
- 8add (4,1)：把点 (4,1) 加进集合，它的次数记为 1（绿色就是刚加入的这个点）。
- 9add (4,4)：把点 (4,4) 加进集合，它的次数记为 1（绿色就是刚加入的这个点）。
- 10count(1,1)：把 (1,1) 设为查询点 q（蓝色高亮）。目标是数出有多少个轴对齐正方形以它为一个角。answer 先记 0。
- 11遍历集合里每个点，挑「和 q 同列(x=1)且不同行」的当竖边搭档。先看 (4,4)：它的 x=4，和 q 不同列，跳过。
- 12再看 (4,1)：x=4 不同列（而且还和 q 同一行），不能当竖边搭档，跳过。
- 13看 (1,4)：x=1 和 q 同列、y=4 又不同行，正好符合，选它当竖边搭档（蓝色）。
- 14q(1,1) 和搭档 p(1,4) 构成左侧竖边，边长 side = |4 − 1| = 3。边长一定，正方形另外两个角就被钉死了。
- 15向右展开：第三个角应是 (qx+side, qy)=(4,1)。去集合里查，(4,1) 存在、出现 1 次（橙色标出）。
- 16第四个角应是 (qx+side, py)=(4,4)。集合里也有、出现 1 次。四个角凑齐，这是一个合法的正方形。
- 17把搭档、右下角、右上角三个点的次数相乘：1×1×1=1。answer 累加，变成 1（四个角一起高亮成绿色）。
- 18同一条竖边还能往左展开：左侧两个角是 (−2,1) 和 (−2,4)，集合里都没有，所以左侧贡献 0 个。
- 19同一列 x=1 里，除了 (1,4) 再没有别的点可当竖边搭档，遍历到此结束。
- 20整趟只数出一个正方形（高亮的四个角），count(1,1) 返回 answer = 1，这就是最终答案。
- 21若此时再 add(4,4) 一次，它的次数变成 2，同一个正方形的方案数就按次数相乘变成 1×1×2=2——这就是为什么要相乘而不是只判存在。
- 22再演一遍 count(4,1)：把 (4,1) 设为查询点 q（蓝色）。同样要数以它为一个角的正方形，answer 重新从 0 开始。
- 23在 x=4 这一列里找搭档：(4,4) 同列且不同行，选它。竖边 (4,1)—(4,4) 的边长 side=3。
- 24这次查询点在右边，往左展开：另两个角是 (1,1) 和 (1,4)，集合里都在（橙色标出）。四角凑齐，又是一个正方形。
- 25相乘累加得 1。注意这和前面 count(1,1) 数到的是「同一个正方形」，只是从不同的角出发去数——返回值仍是 1。
⚠️ 容易写错的地方
✗ 错：只判点「在不在」，忽略重复加点的次数
✓ 对：把三个角的次数相乘累加
同一个点可被重复 add，方案数要按次数相乘，否则少算
✗ 错：把搭档选成「同行」的点
✓ 对：搭档必须同列(px==qx)且不同行(py!=qy)
竖边要竖着，同行的点连出来是横边、定不出向上的正方形，py==qy 还会让 side=0
✗ 错：只往一个方向找另外两个角
✓ 对：向右(+side)和向左(−side)都要查
查询点可能是正方形的左下角，也可能是右下角，两侧都可能有正方形
完整代码（Python / C++ / Java）
Python
class DetectSquares:
def __init__(self):
self.cnt = collections.Counter() # 点 -> 次数
def add(self, p):
self.cnt[(p[0], p[1])] += 1
def count(self, p):
qx, qy = p
ans = 0
for (px, py), c in self.cnt.items():
if px != qx or py == qy: # 只要同列且不同行的搭档
continue
side = abs(py - qy)
for dx in (side, -side): # 向右 / 向左
ans += c * self.cnt[(qx+dx, qy)] * self.cnt[(qx+dx, py)]
return ansC++
class DetectSquares {
map<pair<int,int>,int> cnt;
public:
void add(vector<int> p){ cnt[{p[0],p[1]}]++; }
int count(vector<int> p){
int qx=p[0], qy=p[1], ans=0;
for (auto& [pt,c] : cnt){
int px=pt.first, py=pt.second;
if (px!=qx || py==qy) continue;
int side=abs(py-qy);
for (int dx : {side,-side})
ans += c*cnt[{qx+dx,qy}]*cnt[{qx+dx,py}];
}
return ans;
}
};Java
class DetectSquares {
Map<Long,Integer> cnt = new HashMap<>();
long key(int x,int y){ return (long)x*100003 + y; }
public void add(int[] p){ cnt.merge(key(p[0],p[1]),1,Integer::sum); }
public int count(int[] p){
int qx=p[0], qy=p[1], ans=0;
for (var e : new HashMap<>(cnt).entrySet()){
int px=(int)(e.getKey()/100003), py=(int)(e.getKey()%100003);
if (px!=qx || py==qy) continue;
int side=Math.abs(py-qy);
for (int dx : new int[]{side,-side})
ans += e.getValue()*cnt.getOrDefault(key(qx+dx,qy),0)*cnt.getOrDefault(key(qx+dx,py),0);
}
return ans;
}
}复杂度
add
O(1)
哈希表里给对应点的次数加一
count
O(n)
n 为集合里不同点的个数，遍历一遍找竖边搭档，每个搭档查另两角是 O(1)
空间
O(n)
cnt 哈希表存每个不同点及其次数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 检测正方形 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用「点→次数」的哈希表，而不是只用集合 set？+
因为同一个点可以被重复 add，方案数要按出现次数相乘。用 set 只能判存在、会把重复点的贡献算少，所以必须记次数。
count 里为什么只遍历「竖边搭档」而不是枚举所有点对？+
枚举所有点对找正方形是 O(n²)。固定查询点后，只需找同列的搭档定出一条竖边，另两个角由边长唯一确定、O(1) 查表即可，整体降到 O(n)。
查询点和搭档也可以选成「横边」吗？+
可以，按横边搭档（同行不同列）实现也对，只要保证不重不漏。本解固定用竖边搭档、向左右扩展，逻辑更统一。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 检测正方形 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。