更新题目 Count Squares：数正方形
题目 everpure-count-squares · 修改（rev 8） · · 2026-10-27 00:33
body
@@ -1,14 +1,14 @@ ## TL;DR -- **题**：平面上 n 个点，数一共能组成多少个正方形，每个正方形只算一次。它是 [[q:lc593]]（四点判正方形）的第二问，面试官会要求先给 O(n⁴)，再改到 O(n³)，最后 O(n²)。开写前先问：斜着放的正方形算不算、坐标是不是整数、有没有重复的点、后两级要不要写代码（题目一节的表）。 -- **三级的骨架**（思路第 2 到 4 节）：每升一级，就少枚举一个点、多算出一个点。枚举 4 个点逐个判定，是 O(n⁴)。枚举 2 个点当对角线、再枚举第 3 个点当和两端都相邻的角、第 4 个点算出来去哈希集合里查，是 O(n³)。对角线两端一定，另两个顶点直接算出来、各查一次，是 O(n²)。 -- **O(n²) 的公式**（思路第 4 节）：对角线两端 P = (x1, y1)、Q = (x2, y2)，记 sx = x1 + x2、sy = y1 + y2、dx = x2 − x1、dy = y2 − y1，另两个顶点坐标的两倍是 (sx − dy, sy + dx) 和 (sx + dy, sy − dx)。把所有点的坐标乘 2 存进集合去查，不做除法、不判奇偶。 -- **数几次除几次**（思路第 3、4、5 节）：无序点对当对角线，每个正方形被数 2 次，除以 2。有序点对（跳过 p == q）是 4 次。O(n³) 里第 3 个点有两种选法，是 4 次。点对当边，每个正方形 4 条边各命中一次，也是 4 次。 -- **易错**（易错点一节）：枚举前先去重。不要算出半整数坐标再向下取整。不要用浮点数算中点。 -- **Follow-up**：只算轴平行的，加一个 |dx| = |dy| 的过滤。坐标是小数就先对齐到网格。重复的点要分别算就把「在不在」换成「出现次数相乘」。点一个个加进来、问含某点的正方形数，每次查询 O(n)。答案本身可以有 n² 量级，所以逐个找正方形的算法快不过 O(n²)。 +- **题**（题目一节）：n 个点数能组成几个正方形（每个只算一次），是 [[q:lc593]] 的第二问，要从 $O(n^4)$ 改到 $O(n^3)$ 再到 $O(n^2)$，开写前先问斜的算不算、坐标是不是整数、有没有重复点、后两级写不写代码。 +- **骨架**（思路第 2 到 4 节）：每升一级少枚举一个点、多算一个点，依次是枚举 4 点逐个判定、枚举对角线和一个相邻角再查第 4 点、对角线定了直接算另两个顶点各查一次。 +- **公式**（思路第 4 节）：对角线两端记 $sx = x_1 + x_2$、$sy = y_1 + y_2$、$dx = x_2 - x_1$、$dy = y_2 - y_1$，另两个顶点的两倍坐标是 $(sx - dy, sy + dx)$ 和 $(sx + dy, sy - dx)$，点集坐标也乘 2 去查，不做除法、不判奇偶。 +- **除几次**（思路第 3 到 5 节）：无序点对当对角线除以 2，有序点对（跳过 p == q）、$O(n^3)$ 版、点对当边都除以 4。 +- **易错**（易错点一节）：枚举前先去重，不把半整数坐标向下取整，不用浮点数算中点。 +- **Follow-up**（Follow-up 第 1 到 5 条）：只算轴平行加 $|dx| = |dy|$ 过滤，小数先对齐网格，重复点分别算就把出现次数相乘，动态加点每次查询 $O(n)$，答案可达 $n^2$ 量级所以快不过 $O(n^2)$。 ## 题目 -这道题是 [[q:lc593]] 的第二问。面试官先让你写「给四个点，判断它们是不是一个正方形」，写完接着说：现在平面上有 n 个点，问它们一共能组成多少个正方形。然后分三级追问：先给一个 O(n⁴) 的做法，再优化到 O(n³)，最后优化到 O(n²)。有的面试官不报具体数字，只说「优化到最好」，终点一样是 O(n²)。 +这道题是 [[q:lc593]] 的第二问。面试官先让你写「给四个点，判断它们是不是一个正方形」，写完接着说：现在平面上有 n 个点，问它们一共能组成多少个正方形。然后分三级追问：先给一个 $O(n^4)$ 的做法，再优化到 $O(n^3)$，最后优化到 $O(n^2)$。有的面试官不报具体数字，只说「优化到最好」，终点一样是 $O(n^2)$。 面经里没有人记下函数签名、语言或坐标类型，题面就是口头的一句话。按最自然的理解，输入是一个点的列表，每个点是一对整数坐标 (x, y)【推断，所有帖子都只说「点」和「坐标」，没人提过小数】。输出是一个整数。可以主动把签名写出来，让面试官确认： @@ -26,5 +26,5 @@ ``` -答案是 2。一个是边长 1、和坐标轴平行的正方形，顶点 (0, 0)、(1, 0)、(1, 1)、(0, 1)。另一个是斜着放的，顶点 (1, 0)、(2, 1)、(1, 2)、(0, 1)，四条边都是从一个点往斜对角走一格，长度都是 √2。如果只数和坐标轴平行的，答案是 1。 +答案是 2。一个是边长 1、和坐标轴平行的正方形，顶点 (0, 0)、(1, 0)、(1, 1)、(0, 1)。另一个是斜着放的，顶点 (1, 0)、(2, 1)、(1, 2)、(0, 1)，四条边都是从一个点往斜对角走一格，长度都是 $\sqrt{2}$。如果只数和坐标轴平行的，答案是 1。 ### 开写之前要问清楚的 @@ -37,15 +37,15 @@ | 坐标是整数还是小数？ | 面经没说，整数是默认【推断】 | 小数要先对齐到网格再用整数做法，见 Follow-up 第 2 条 | | 输入里有没有重复的点？ | 面经没说。一亩三分地帖子页面上有一段网站自动生成的 AI 摘要（下文简称「站方 AI 摘要」），里面写了「无重复点」，那不是发帖人写的。按「没有」处理，但代码开头先用集合去重，有重复也不会错 | 如果重复的点要当成不同的点、各算一遍，把「在不在」换成「出现次数相乘」，见 Follow-up 第 3 条 | -| O(n³)、O(n²) 要写代码还是说思路？ | 2017 年和 2026-06 各有一位发帖人说讲清思路就够了，2026-06 那位还说不用推数学公式。但要按「随时能写」准备，O(n²) 的代码只有十行左右 | 要写就写「代码」一节那个版本 | -| n 有多大？ | 没人记下来。面试官要 O(n²)，说明 n 大概在几千的量级【推断】 | n 再大也没有更快的通用做法，见 Follow-up 第 5 条 | -| 能用哈希集合吗？ | 能，面经里的做法都靠它 | 不让用就把查找换成排序加二分，每级多一个 log n，见 Follow-up 第 6 条 | +| $O(n^3)$、$O(n^2)$ 要写代码还是说思路？ | 2017 年和 2026-06 各有一位发帖人说讲清思路就够了，2026-06 那位还说不用推数学公式。但要按「随时能写」准备，$O(n^2)$ 的代码只有十行左右 | 要写就写「代码」一节那个版本 | +| n 有多大？ | 没人记下来。面试官要 $O(n^2)$，说明 n 大概在几千的量级【推断】 | n 再大也没有更快的通用做法，见 Follow-up 第 5 条 | +| 能用哈希集合吗？ | 能，面经里的做法都靠它 | 不让用就把查找换成排序加二分，每级多一个 $\log n$，见 Follow-up 第 6 条 | ## 面经里怎么考的 -这道题在 [[c:everpure]]（原 Pure Storage）从 2017 年一直考到 2026 年，题面和追问几乎没变。最早的是 2017 年一篇电话面试帖子：给平面上四个点、每个点是 (x, y) 坐标，判断能不能组成正方形。follow-up 是给 n 个点问能组成多少个，要求先 O(n⁴)、再改进到 O(n³)、最后到 O(n²)。2025-12 和 2026-06 两篇电话面试帖子记下的追问顺序和它一模一样。2025-06 一篇现场面试（onsite）的帖子里，这道题占一轮代码面，面试官只说「优化到最好的时间」，没有报中间那一级。2026-04 一篇电话面试帖子的发帖人直接给了 O(n²)，没提中间两级。求职社区 Taro 上 2025-10 一篇 Senior SDE 的面经也列了这道题，没说在哪一轮。 - -面试官认可的做法，帖子里记下了两种说法。2017 年那篇的发帖人在评论里回答别人时讲了 O(n²)：任取两个点当正方形的一条对角线，算出另一条对角线的两个端点，去集合里查。他还说 follow-up 不用写代码，讲清想法就行。提问的人原本想的是「任取两点当边、查另外两点」，觉得用哈希集合做不出来，其实也能做，见思路第 5 节。2026-04 那篇写得最具体：四点判定算 6 个两两距离，4 条相等的边、2 条相等的对角线，对角线是边的 √2 倍（照字面用浮点数比「√2 倍」会出错，要比距离的平方，见 [[q:lc593]]）。数个数是把每对点当对角线、查另外两个端点在不在集合里，命中的次数除以 2，因为每个正方形有两条对角线。2026-06 那位说不用推数学公式，思路对了面试官就认。没有一篇帖子写下 O(n³) 那一级怎么做，2025-12 那篇有人在评论里问，发帖人没有展开，所以思路第 3 节的做法是按「从 O(n⁴) 到 O(n²) 中间最自然的一步」推出来的【推断】。 - -题面留白的地方没人问清过：2018 年有人在 2017 年那篇帖子下面问「正方形的边要不要平行于坐标轴」，没有人回答，这就是题目一节那张表第一行要先问的原因。站方 AI 摘要里的示例输入输出、「n 不超过 10⁴」「无重复点」「只算轴平行」都不是发帖人写的，不要拿它当题面。 +这道题在 [[c:everpure]]（原 Pure Storage）从 2017 年一直考到 2026 年，题面和追问几乎没变。最早的是 2017 年一篇电话面试帖子：给平面上四个点、每个点是 (x, y) 坐标，判断能不能组成正方形。follow-up 是给 n 个点问能组成多少个，要求先 $O(n^4)$、再改进到 $O(n^3)$、最后到 $O(n^2)$。2025-12 和 2026-06 两篇电话面试帖子记下的追问顺序和它一模一样。2025-06 一篇现场面试（onsite）的帖子里，这道题占一轮代码面，面试官只说「优化到最好的时间」，没有报中间那一级。2026-04 一篇电话面试帖子的发帖人直接给了 $O(n^2)$，没提中间两级。求职社区 Taro 上 2025-10 一篇 Senior SDE 的面经也列了这道题，没说在哪一轮。 + +面试官认可的做法，帖子里记下了两种说法。2017 年那篇的发帖人在评论里回答别人时讲了 $O(n^2)$：任取两个点当正方形的一条对角线，算出另一条对角线的两个端点，去集合里查。他还说 follow-up 不用写代码，讲清想法就行。提问的人原本想的是「任取两点当边、查另外两点」，觉得用哈希集合做不出来，其实也能做，见思路第 5 节。2026-04 那篇写得最具体：四点判定算 6 个两两距离，4 条相等的边、2 条相等的对角线，对角线是边的 $\sqrt{2}$ 倍（照字面用浮点数比「$\sqrt{2}$ 倍」会出错，要比距离的平方，见 [[q:lc593]]）。数个数是把每对点当对角线、查另外两个端点在不在集合里，命中的次数除以 2，因为每个正方形有两条对角线。2026-06 那位说不用推数学公式，思路对了面试官就认。没有一篇帖子写下 $O(n^3)$ 那一级怎么做，2025-12 那篇有人在评论里问，发帖人没有展开，所以思路第 3 节的做法是按「从 $O(n^4)$ 到 $O(n^2)$ 中间最自然的一步」推出来的【推断】。 + +题面留白的地方没人问清过：2018 年有人在 2017 年那篇帖子下面问「正方形的边要不要平行于坐标轴」，没有人回答，这就是题目一节那张表第一行要先问的原因。站方 AI 摘要里的示例输入输出、「n 不超过 $10^4$」「无重复点」「只算轴平行」都不是发帖人写的，不要拿它当题面。 教训是这道题要**稳拿**。它几乎总和 Fire Event（[[q:everpure-fire-event]]）配成一组：2017 年那位发帖人两次电话面试都是这两道，2025-06 的现场面试和 2025-12 的电话面试也是。没有人说自己卡在数正方形上。2025-12 的发帖人觉得两轮都答得不错，还是被拒了，2026-06 的发帖人认为自己是在多线程那轮的追问上被拒的。2026-03 还有一篇现场面试的帖子说，两轮都是 2017 年那篇帖子里整理的题、面试官一直追问和要优化，可见这份题单到 2026 年还在用。 @@ -59,9 +59,15 @@ #### 向量（vector） -设 P = (x1, y1)、Q = (x2, y2)，从 P 走到 Q「要走多少」记成 Q − P = (x2 − x1, y2 − y1)，这就是一个向量。点加上向量得到新的点。两个向量 a = (a1, a2)、b = (b1, b2) 的点积（dot product）是 a·b = a1·b1 + a2·b2。向量长度的平方就是它和自己的点积，记成 |a|² = a·a = a1² + a2²。点积等于 0 就表示两个向量垂直（perpendicular），这是判定垂直最省事的办法，不用算角度。后面会反复用一个展开式：|a + b|² = (a + b)·(a + b) = |a|² + 2 a·b + |b|²，同理 |a − b|² = |a|² − 2 a·b + |b|²。 +设 $P = (x_1, y_1)$、$Q = (x_2, y_2)$，从 P 走到 Q「要走多少」记成 $Q - P = (x_2 - x_1, y_2 - y_1)$，这就是一个向量。点加上向量得到新的点。两个向量 $a = (a_1, a_2)$、$b = (b_1, b_2)$ 的点积（dot product）是 $a \cdot b = a_1 b_1 + a_2 b_2$。向量长度的平方就是它和自己的点积，记成 $|a|^2 = a \cdot a = a_1^2 + a_2^2$。点积等于 0 就表示两个向量垂直（perpendicular），这是判定垂直最省事的办法，不用算角度。后面会反复用一个展开式： + +$$ +|a + b|^2 = (a + b) \cdot (a + b) = |a|^2 + 2\, a \cdot b + |b|^2 +$$ + +同理 $|a - b|^2 = |a|^2 - 2\, a \cdot b + |b|^2$。 #### 把向量转 90° -向量 (x, y) 逆时针转 90° 得到 (−y, x)。验证一下：朝东的 (1, 0) 变成朝北的 (0, 1)，朝北的 (0, 1) 变成朝西的 (−1, 0)。顺时针转 90° 是 (y, −x)，和逆时针的结果正好反向。转完的向量和原向量点积是 x·(−y) + y·x = 0，确实垂直，长度也没变。反过来也成立：**对任何非零向量 h，和它垂直、而且和它一样长的向量只有两个，就是 h 转 90° 的两个结果**。理由是，设 h = (hx, hy)，和它垂直的 (a, b) 满足 a·hx + b·hy = 0，也就是 (a, b) 是 (−hy, hx) 的某个倍数 t·(−hy, hx)（hx 不为 0 时 a = −b·hy/hx，取 t = b/hx 就看出来。hy 不为 0 时同理）。再要求长度相等，t 只能是 1 或 −1。 +向量 $(x, y)$ 逆时针转 90° 得到 $(-y, x)$。验证一下：朝东的 (1, 0) 变成朝北的 (0, 1)，朝北的 (0, 1) 变成朝西的 (−1, 0)。顺时针转 90° 是 $(y, -x)$，和逆时针的结果正好反向。转完的向量和原向量点积是 $x \cdot (-y) + y \cdot x = 0$，确实垂直，长度也没变。反过来也成立：**对任何非零向量 h，和它垂直、而且和它一样长的向量只有两个，就是 h 转 90° 的两个结果**。理由是，设 $h = (h_x, h_y)$，和它垂直的 $(a, b)$ 满足 $a h_x + b h_y = 0$，也就是 $(a, b)$ 是 $(-h_y, h_x)$ 的某个倍数 $t \cdot (-h_y, h_x)$（$h_x$ 不为 0 时 $a = -b h_y / h_x$，取 $t = b / h_x$ 就看出来。$h_y$ 不为 0 时同理）。再要求长度相等，t 只能是 1 或 −1。 #### 正方形的两条对角线（diagonal） @@ -69,10 +75,10 @@ 正方形是四条边等长、四个角都是直角的四边形。连接不相邻两个顶点的线段叫对角线，一共两条。两个方向的事实都要用： -- *正方形的两条对角线一样长、互相垂直、而且中点重合。* 把正方形的顶点按绕一圈的顺序叫 P、R、Q、S，相邻两条边的向量叫 u = R − P、v = Q − R，它们等长且垂直（|u| = |v|，u·v = 0），再往下两条边是 −u、−v。两条对角线是 PQ 和 RS：Q − P = u + v，S − R = v − u。长度：|u + v|² = |u|² + 2 u·v + |v|² = 2|u|²，|v − u|² 同样是 2|u|²，相等。垂直：(u + v)·(v − u) = |v|² − |u|² = 0。中点：PQ 的中点是 P + (u + v)/2，RS 的中点是 R + (v − u)/2 = P + u + (v − u)/2 = P + (u + v)/2，相同。 -- *反过来：两条线段一样长、互相垂直、中点重合，它们的四个端点就是一个正方形。* 这一条是 O(n²) 做法的依据。设公共中点是 M，第一条线段从 M 出发的半截是向量 h（两个端点是 M − h 和 M + h），第二条线段和它垂直、一样长，所以它的半截是 h 转 90° 得到的 r。四个端点按 P = M − h、R = M + r、Q = M + h、S = M − r 的顺序绕一圈，相邻两点之差依次是 R − P = h + r、Q − R = h − r、S − Q = −h − r、P − S = r − h。因为 h·r = 0，|h + r|² = |h|² + |r|² = 2|h|²，另外三条边同理，四条边一样长。相邻两条边的点积 (h + r)·(h − r) = |h|² − |r|² = 0，(h − r)·(−h − r) = −|h|² + |r|² = 0，其余两处同理，所以每个角都是直角。四条边等长、四个角是直角，就是正方形。 +- *正方形的两条对角线一样长、互相垂直、而且中点重合。* 把正方形的顶点按绕一圈的顺序叫 P、R、Q、S，相邻两条边的向量叫 $u = R - P$、$v = Q - R$，它们等长且垂直（$|u| = |v|$，$u \cdot v = 0$），再往下两条边是 $-u$、$-v$。两条对角线是 PQ 和 RS：$Q - P = u + v$，$S - R = v - u$。长度：$|u + v|^2 = |u|^2 + 2\, u \cdot v + |v|^2 = 2|u|^2$，$|v - u|^2$ 同样是 $2|u|^2$，相等。垂直：$(u + v) \cdot (v - u) = |v|^2 - |u|^2 = 0$。中点：PQ 的中点是 $P + (u + v)/2$，RS 的中点是 $R + (v - u)/2 = P + u + (v - u)/2 = P + (u + v)/2$，相同。 +- *反过来：两条线段一样长、互相垂直、中点重合，它们的四个端点就是一个正方形。* 这一条是 $O(n^2)$ 做法的依据。设公共中点是 M，第一条线段从 M 出发的半截是向量 h（两个端点是 $M - h$ 和 $M + h$），第二条线段和它垂直、一样长，所以它的半截是 h 转 90° 得到的 r。四个端点按 $P = M - h$、$R = M + r$、$Q = M + h$、$S = M - r$ 的顺序绕一圈，相邻两点之差依次是 $R - P = h + r$、$Q - R = h - r$、$S - Q = -h - r$、$P - S = r - h$。因为 $h \cdot r = 0$，$|h + r|^2 = |h|^2 + |r|^2 = 2|h|^2$，另外三条边同理，四条边一样长。相邻两条边的点积 $(h + r) \cdot (h - r) = |h|^2 - |r|^2 = 0$，$(h - r) \cdot (-h - r) = -|h|^2 + |r|^2 = 0$，其余两处同理，所以每个角都是直角。四条边等长、四个角是直角，就是正方形。 #### 哈希集合和 `combinations` -「查某个点在不在」用 Python 的 `set`，点存成元组 `(x, y)`。标准库 `itertools.combinations(pts, k)` 依次给出 `pts` 里所有 k 个元素的组合，每个组合只出现一次、不分顺序。下面说的「无序点对（unordered pair）」就是 `combinations(pts, 2)` 给出的东西：P、Q 和 Q、P 算同一对，一共 n(n − 1)/2 对。 +「查某个点在不在」用 Python 的 `set`，点存成元组 `(x, y)`。标准库 `itertools.combinations(pts, k)` 依次给出 `pts` 里所有 k 个元素的组合，每个组合只出现一次、不分顺序。下面说的「无序点对（unordered pair）」就是 `combinations(pts, 2)` 给出的东西：P、Q 和 Q、P 算同一对，一共 $n(n - 1)/2$ 对。 ### 2. O(n⁴)：枚举四个点，逐个判定 @@ -94,13 +100,13 @@ ``` -这个版本是对的，因为每个正方形就是点集里的某 4 个点，`combinations` 把每个 4 点组合恰好产生一次，所以每个正方形恰好被数 1 次，不用除。代价是组合数 C(n, 4) = n(n − 1)(n − 2)(n − 3)/24 ≈ n⁴/24，每组判定是常数时间。n = 80 时有 158 万组，n = 1000 就是 4 × 10¹⁰ 组，跑不完。 +这个版本是对的，因为每个正方形就是点集里的某 4 个点，`combinations` 把每个 4 点组合恰好产生一次，所以每个正方形恰好被数 1 次，不用除。代价是组合数 $C(n, 4) = n(n - 1)(n - 2)(n - 3)/24 \approx n^4/24$，每组判定是常数时间。n = 80 时有 158 万组，n = 1000 就是 $4 \times 10^{10}$ 组，跑不完。 ### 3. O(n³)：枚举三个点，算出第四个【推断】 -没有一篇面经写下面试官认可的 O(n³) 做法，下面是从 O(n⁴) 往 O(n²) 走时最自然的一步。面试里先一句话说出想法，面试官心里有别的版本自然会把你往那边带。 - -想省掉一层循环，思路是：**正方形被三个顶点唯一确定，第四个顶点可以算出来，算出来就去集合里查，不用枚举**。为了让「第四个顶点」有个现成的公式，给三个点分配角色：P、Q 当一条对角线的两端，R 是和 P、Q 都相邻的一个顶点（这样的顶点有两个，任取其一，另一个就是要算的 S）。这样 S 就是 R 关于中点 M = (P + Q)/2 的对称点，S = 2M − R = P + Q − R（对角线互相平分，R 和 S 到 M 的距离相等、方向相反）。 - -R 必须满足两个条件才可能是这个正方形的顶点：到 P 和到 Q 一样远（正方形的每个顶点到相邻两个顶点等距），并且 |RP|² + |RQ|² = |PQ|²（勾股定理的逆定理：三条边满足这个等式，R 处就是直角）。两个条件都满足，再去集合里查 S。只查等距是不够的：那样 R 可以是 PQ 垂直平分线上的任何一点，算出的 S 是菱形（rhombus，四条边相等、但角不一定是直角的四边形）的第四个顶点，菱形也会被数进来（测试用例里有一个菱形的反例）。 +没有一篇面经写下面试官认可的 $O(n^3)$ 做法，下面是从 $O(n^4)$ 往 $O(n^2)$ 走时最自然的一步。面试里先一句话说出想法，面试官心里有别的版本自然会把你往那边带。 + +想省掉一层循环，思路是：**正方形被三个顶点唯一确定，第四个顶点可以算出来，算出来就去集合里查，不用枚举**。为了让「第四个顶点」有个现成的公式，给三个点分配角色：P、Q 当一条对角线的两端，R 是和 P、Q 都相邻的一个顶点（这样的顶点有两个，任取其一，另一个就是要算的 S）。这样 S 就是 R 关于中点 $M = (P + Q)/2$ 的对称点，$S = 2M - R = P + Q - R$（对角线互相平分，R 和 S 到 M 的距离相等、方向相反）。 + +R 必须满足两个条件才可能是这个正方形的顶点：到 P 和到 Q 一样远（正方形的每个顶点到相邻两个顶点等距），并且 $|RP|^2 + |RQ|^2 = |PQ|^2$（勾股定理的逆定理：三条边满足这个等式，R 处就是直角）。两个条件都满足，再去集合里查 S。只查等距是不够的：那样 R 可以是 PQ 垂直平分线上的任何一点，算出的 S 是菱形（rhombus，四条边相等、但角不一定是直角的四边形）的第四个顶点，菱形也会被数进来（测试用例里有一个菱形的反例）。 ```python @@ -123,14 +129,14 @@ ``` -这个版本是对的，要分两半看。先看每次命中都是真的正方形。记 M 是 PQ 的中点，h = (Q − P)/2，于是 P = M − h、Q = M + h。再记 r = R − M，于是 R − P = r + h、R − Q = r − h。两个条件翻译成向量： - -- 等距：|r + h|² = |r − h|²，按第 1 节的展开式，左边是 |r|² + 2 r·h + |h|²，右边是 |r|² − 2 r·h + |h|²，相等就是 r·h = 0，r 和 h 垂直。 -- 直角：|r + h|² + |r − h|² = |2h|²，左边展开是 2|r|² + 2|h|²，右边是 4|h|²，所以 |r|² = |h|²，r 和 h 一样长。 - -和 h 垂直又一样长的向量只有 h 转 90° 得到的两个（第 1 节），所以 R = M + r 只可能在两个位置。而 S = P + Q − R = 2M − R = M − r。于是线段 RS 的中点也是 M，长度 |RS| = 2|r| = 2|h| = |PQ|，方向 r 和 h 垂直。两条线段 PQ、RS 等长、垂直、中点重合，按第 1 节的结论四个端点就是正方形。R 和 P 重合的情况不用单独防：那时 R 到 P 的距离是 0、到 Q 的距离不是 0，「等距」这一条就把它挡掉了。 +这个版本是对的，要分两半看。先看每次命中都是真的正方形。记 M 是 PQ 的中点，$h = (Q - P)/2$，于是 $P = M - h$、$Q = M + h$。再记 $r = R - M$，于是 $R - P = r + h$、$R - Q = r - h$。两个条件翻译成向量： + +- 等距：$|r + h|^2 = |r - h|^2$，按第 1 节的展开式，左边是 $|r|^2 + 2\, r \cdot h + |h|^2$，右边是 $|r|^2 - 2\, r \cdot h + |h|^2$，相等就是 $r \cdot h = 0$，r 和 h 垂直。 +- 直角：$|r + h|^2 + |r - h|^2 = |2h|^2$，左边展开是 $2|r|^2 + 2|h|^2$，右边是 $4|h|^2$，所以 $|r|^2 = |h|^2$，r 和 h 一样长。 + +和 h 垂直又一样长的向量只有 h 转 90° 得到的两个（第 1 节），所以 $R = M + r$ 只可能在两个位置。而 $S = P + Q - R = 2M - R = M - r$。于是线段 RS 的中点也是 M，长度 $|RS| = 2|r| = 2|h| = |PQ|$，方向 r 和 h 垂直。两条线段 PQ、RS 等长、垂直、中点重合，按第 1 节的结论四个端点就是正方形。R 和 P 重合的情况不用单独防：那时 R 到 P 的距离是 0、到 Q 的距离不是 0，「等距」这一条就把它挡掉了。 再看不会漏：任何一个正方形，它的某两个对角顶点一定会在某一轮被当成 P、Q（`combinations` 枚举了所有无序点对），另两个顶点之一会被内层循环扫到当 R，第四个顶点在集合里，命中。 -返回值要除以 4，是因为同一个正方形有 2 条对角线，每条对角线下 R 又有 2 种选法（另外两个顶点各一次），所以被命中 4 次，`hits` 一定是 4 的倍数。代价是 n(n − 1)/2 对乘以 n 个 R，是 O(n³)。 +返回值要除以 4，是因为同一个正方形有 2 条对角线，每条对角线下 R 又有 2 种选法（另外两个顶点各一次），所以被命中 4 次，`hits` 一定是 4 的倍数。代价是 $n(n - 1)/2$ 对乘以 n 个 R，是 $O(n^3)$。 另一种组织方式是枚举任意 3 个点、不预先分配角色，用三个距离判断它们能不能当正方形的三个顶点（两条短边相等、长边的平方是短边的 2 倍），找出直角所在的顶点，第四点同样是另外两点之和减去直角顶点。每个正方形有 4 个三点子集，也除以 4。它和上面的版本结果一样（测试用例里两种都跑了）。上面那种的好处是内层循环「在 n 个点里找 R」正好是下一级要去掉的东西。 @@ -138,12 +144,13 @@ ### 4. O(n²)：对角线一定，另两个顶点直接算 -第 3 节的「为什么对」已经说明：P、Q 定了以后，R 只能在 M + r 和 M − r 两个位置，r 是半条对角线 h 转 90°。那内层循环「在 n 个点里找 R」就是多余的，直接算出这两个位置、各查一次就行。 - -设 P = (x1, y1)、Q = (x2, y2)。中点 M = ((x1 + x2)/2, (y1 + y2)/2)，半条对角线 h = ((x2 − x1)/2, (y2 − y1)/2)，h 转 90° 是 r = (−(y2 − y1)/2, (x2 − x1)/2)。另两个顶点是 A = M + r 和 B = M − r。这里有除以 2，想全程留在整数里，就把算出的顶点坐标和集合里存的点坐标都乘 2。记 sx = x1 + x2、sy = y1 + y2、dx = x2 − x1、dy = y2 − y1，则 - -- 2A = (sx − dy, sy + dx) -- 2B = (sx + dy, sy − dx) - -要查的是「A 在不在点集里」，等价于「2A 在不在所有点坐标乘 2 的集合里」。所以把每个点 (x, y) 存成 (2x, 2y)，直接拿 2A、2B 去查，一次除法都不做。如果 sx − dy 是奇数，说明 A 的真实坐标是半整数，不可能是输入里的点。而集合里存的全是偶数，奇数自然查不到，连判奇偶都省了。顺便一提，2A、2B 的四个坐标奇偶性总是相同的（(sx − dy) − (sy + dx) = 2x1 − 2y2 是偶数，(sx + dy) − (sx − dy) = 2dy 也是偶数），所以如果你更愿意写「判奇偶再除以 2」的版本，判一个坐标就够。 +第 3 节的「为什么对」已经说明：P、Q 定了以后，R 只能在 $M + r$ 和 $M - r$ 两个位置，r 是半条对角线 h 转 90°。那内层循环「在 n 个点里找 R」就是多余的，直接算出这两个位置、各查一次就行。 + +设 $P = (x_1, y_1)$、$Q = (x_2, y_2)$。中点 $M = \left(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}\right)$，半条对角线 $h = \left(\frac{x_2 - x_1}{2}, \frac{y_2 - y_1}{2}\right)$，h 转 90° 是 $r = \left(-\frac{y_2 - y_1}{2}, \frac{x_2 - x_1}{2}\right)$。另两个顶点是 $A = M + r$ 和 $B = M - r$。这里有除以 2，想全程留在整数里，就把算出的顶点坐标和集合里存的点坐标都乘 2。记 $sx = x_1 + x_2$、$sy = y_1 + y_2$、$dx = x_2 - x_1$、$dy = y_2 - y_1$，则 + +$$ +2A = (sx - dy,\ sy + dx), \qquad 2B = (sx + dy,\ sy - dx) +$$ + +要查的是「A 在不在点集里」，等价于「2A 在不在所有点坐标乘 2 的集合里」。所以把每个点 $(x, y)$ 存成 $(2x, 2y)$，直接拿 2A、2B 去查，一次除法都不做。如果 $sx - dy$ 是奇数，说明 A 的真实坐标是半整数，不可能是输入里的点。而集合里存的全是偶数，奇数自然查不到，连判奇偶都省了。顺便一提，2A、2B 的四个坐标奇偶性总是相同的（$(sx - dy) - (sy + dx) = 2x_1 - 2y_2$ 是偶数，$(sx + dy) - (sx - dy) = 2dy$ 也是偶数），所以如果你更愿意写「判奇偶再除以 2」的版本，判一个坐标就够。 这就是面经里 2017 年和 2026-04 两位发帖人说的做法。完整代码在「代码」一节，下面按它走一遍题目里的例子。 @@ -151,7 +158,7 @@ 6 个点有 15 对。对角线 (0, 0)–(1, 1)：sx = 1、sy = 1、dx = 1、dy = 1，2A = (0, 2)、2B = (2, 0)，也就是 A = (0, 1)、B = (1, 0)，都在点集里，命中。对角线 (1, 0)–(1, 2)：sx = 2、sy = 2、dx = 0、dy = 2，2A = (0, 2)、2B = (4, 2)，即 (0, 1) 和 (2, 1)，命中，这就是那个斜的正方形。对角线 (0, 0)–(2, 1)：sx = 2、sy = 1、dx = 2、dy = 1，2A = (1, 3)、2B = (3, −1)，坐标是奇数，集合里没有，跳过。对角线 (1, 0)–(2, 1)：2A = (2, 2) 即 (1, 1)，在。2B = (4, 0) 即 (2, 0)，不在，跳过。15 对里命中 4 次（另两次是 (0, 1)–(1, 0) 和 (0, 1)–(2, 1)，分别是两个正方形的另一条对角线），除以 2 得 2。 -这个做法是对的。每次命中，PQ 和 AB 两条线段等长（|AB| = 2|r| = 2|h| = |PQ|）、垂直（r 是 h 转 90°）、中点都是 M，按第 1 节是正方形，不会多数。任何正方形的一条对角线一定被枚举到，那时算出的 A、B 正是它另两个顶点，不会漏。除以 2 是因为一个正方形恰有 2 条对角线，每条命中一次，`hits` 一定是偶数。如果用两层循环枚举有序对、跳过 p == q，(P, Q) 和 (Q, P) 算出的 A、B 是同一对（只是互换），每个正方形命中 4 次，这时要除以 4，只除 2 就得到两倍的答案。如果连 p == q 也不跳过，错得更多：一个点和自己配对时 dx = dy = 0，算出的「另两个顶点」就是它自己，每个点都多一次假命中，除以 4 也救不回来。 - -代价是 n(n − 1)/2 对，每对两次集合查找，O(n²) 时间。集合 O(n) 空间。 +这个做法是对的。每次命中，PQ 和 AB 两条线段等长（$|AB| = 2|r| = 2|h| = |PQ|$）、垂直（r 是 h 转 90°）、中点都是 M，按第 1 节是正方形，不会多数。任何正方形的一条对角线一定被枚举到，那时算出的 A、B 正是它另两个顶点，不会漏。除以 2 是因为一个正方形恰有 2 条对角线，每条命中一次，`hits` 一定是偶数。如果用两层循环枚举有序对、跳过 p == q，(P, Q) 和 (Q, P) 算出的 A、B 是同一对（只是互换），每个正方形命中 4 次，这时要除以 4，只除 2 就得到两倍的答案。如果连 p == q 也不跳过，错得更多：一个点和自己配对时 $dx = dy = 0$，算出的「另两个顶点」就是它自己，每个点都多一次假命中，除以 4 也救不回来。 + +代价是 $n(n - 1)/2$ 对，每对两次集合查找，$O(n^2)$ 时间。集合 $O(n)$ 空间。 ### 5. 另一种 O(n²)：两点当边 @@ -159,5 +166,5 @@ 2017 年帖子评论区有人想的是「任取两点当一条边、查另外两点」，觉得用哈希集合做不出来。其实能做，只是要想清楚两件事：一条边两侧各有一个候选正方形，两侧都要查。每个正方形有 4 条边，所以除以 4。 -枚举无序点对 P、Q 当正方形的一条边，边向量 v = Q − P = (dx, dy)，把它转 90° 得到 w = (−dy, dx)（这里用 w，和第 4 节由半条对角线转出来的 r 不是一个东西）。正方形要么在边的这一侧（另两个顶点是 P + w、Q + w），要么在那一侧（P − w、Q − w），两侧各查一次： +枚举无序点对 P、Q 当正方形的一条边，边向量 $v = Q - P = (dx, dy)$，把它转 90° 得到 $w = (-dy, dx)$（这里用 w，和第 4 节由半条对角线转出来的 r 不是一个东西）。正方形要么在边的这一侧（另两个顶点是 $P + w$、$Q + w$），要么在那一侧（$P - w$、$Q - w$），两侧各查一次： ```python @@ -176,5 +183,5 @@ ``` -这个做法是对的。命中时，P、Q、Q + w、P + w 四个点相邻之差依次是 v、w、−v、−w，等长且相邻垂直，是正方形。任何正方形的任何一条边都会被枚举到，那时正方形所在的那一侧会命中。除以 4 是因为每次命中对应唯一的一个「正方形和它的一条边」：P、Q 是那条边，w 取哪个方向决定是哪一侧的正方形。一条边两侧都有点时两侧各命中一次，但那是两个不同的正方形，各记在自己的这条边上。每个正方形有 4 条边，每条边作为无序点对恰好枚举一次，所以 `hits` 恰好是正方形数的 4 倍。这个版本不需要乘 2，因为整点加整数向量还是整点。 +这个做法是对的。命中时，P、Q、$Q + w$、$P + w$ 四个点相邻之差依次是 $v$、$w$、$-v$、$-w$，等长且相邻垂直，是正方形。任何正方形的任何一条边都会被枚举到，那时正方形所在的那一侧会命中。除以 4 是因为每次命中对应唯一的一个「正方形和它的一条边」：P、Q 是那条边，w 取哪个方向决定是哪一侧的正方形。一条边两侧都有点时两侧各命中一次，但那是两个不同的正方形，各记在自己的这条边上。每个正方形有 4 条边，每条边作为无序点对恰好枚举一次，所以 `hits` 恰好是正方形数的 4 倍。这个版本不需要乘 2，因为整点加整数向量还是整点。 两种写法复杂度一样，边的版本每对最多查 4 次，对角线版最多 2 次（实测耗时见测试用例）。面经里的人用的是对角线版，Follow-up 第 1 条（只算轴平行）和第 4 条（动态加点）也是对角线版更顺手，所以主推第 4 节的写法。 @@ -182,5 +189,5 @@ ## 代码 -面试里写这个版本，推导在思路第 4 节。要点三句话：先去重，再把坐标乘 2 存集合。无序点对当对角线，另两个顶点的两倍坐标是 (sx − dy, sy + dx) 和 (sx + dy, sy − dx)。命中数除以 2。 +面试里写这个版本，推导在思路第 4 节。要点三句话：先去重，再把坐标乘 2 存集合。无序点对当对角线，另两个顶点的两倍坐标是 $(sx - dy, sy + dx)$ 和 $(sx + dy, sy - dx)$。命中数除以 2。 ```python @@ -205,10 +212,10 @@ | 版本 | 时间 | 空间 | | --- | --- | --- | -| 第 2 节，枚举 4 点 | C(n, 4) ≈ n⁴/24 | O(n) | -| 第 3 节，对角线 + 枚举第三点 | n(n − 1)/2 × n = O(n³) | O(n) | -| 第 4 节，对角线直接算 | n(n − 1)/2 × 2 次查找 = O(n²) | O(n) | -| 第 5 节，两点当边 | n(n − 1)/2 × 4 次查找 = O(n²) | O(n) | - -哈希集合的查找按平均 O(1) 算。空间都是存一份点集（第 4 节多存一份乘 2 的副本，还是 O(n)）。 +| 第 2 节，枚举 4 点 | $C(n, 4) \approx n^4/24$ | $O(n)$ | +| 第 3 节，对角线 + 枚举第三点 | $n(n - 1)/2 \times n = O(n^3)$ | $O(n)$ | +| 第 4 节，对角线直接算 | $n(n - 1)/2 \times 2$ 次查找 = $O(n^2)$ | $O(n)$ | +| 第 5 节，两点当边 | $n(n - 1)/2 \times 4$ 次查找 = $O(n^2)$ | $O(n)$ | + +哈希集合的查找按平均 $O(1)$ 算。空间都是存一份点集（第 4 节多存一份乘 2 的副本，还是 $O(n)$）。 ## 易错点 @@ -217,18 +224,18 @@ - **有序点对只除以 2**（思路第 4 节）：两层循环枚举有序对，即使跳过 p == q，每个正方形也命中 4 次，只除 2 答案翻倍。 -- **枚举的是输入列表，没先去重**（代码一节）：一个点和它的副本配成「对角线」，dx = dy = 0，算出的「另两个顶点」就是它自己，凭空多出命中。 +- **枚举的是输入列表，没先去重**（代码一节）：一个点和它的副本配成「对角线」，$dx = dy = 0$，算出的「另两个顶点」就是它自己，凭空多出命中。 - **除以 2 再取整、不判奇偶**（思路第 4 节）：`(sx - dy) // 2` 把半整数向下取整，可能正好落在某个真实点上，成了假命中。 -- **用浮点数算中点**（Follow-up 第 2 条）：小数坐标算出的顶点和输入差在最后一位、对不上。整数坐标大到 2⁵² 以上时，半整数顶点会被舍入到真实点上。整数做法不做除法，两种问题都没有。 +- **用浮点数算中点**（Follow-up 第 2 条）：小数坐标算出的顶点和输入差在最后一位、对不上。整数坐标大到 $2^{52}$ 以上时，半整数顶点会被舍入到真实点上。整数做法不做除法，两种问题都没有。 - **默认只有轴平行的正方形**（题目一节的表）：面试官没说，自己要先确认，自测的例子也要包含斜的那种。 -- **O(n³) 版漏掉「直角」条件**（思路第 3 节）：只查等距，菱形也会被数成正方形。 +- **$O(n^3)$ 版漏掉「直角」条件**（思路第 3 节）：只查等距，菱形也会被数成正方形。 ## 测试用例 -代码都在 2026-10-24 用 Python 3.12.10 实际跑过（`python -I`）。另用一个脚本把本页每个 Python 代码块单独取出、在干净的命名空间里执行、用题目里的例子各调用一次，结果和下面一致。六个正确版本（O(n⁴) 枚举、O(n³) 对角线加第三点、O(n³) 任意三点、O(n²) 对角线乘 2、O(n²) 对角线判奇偶、O(n²) 边）放在同一组输入上比： - -- **题目里的例子**（6 个点）：六个版本都返回 2，O(n⁴) 版列出的两个正方形就是题目里写的那两个。15 个无序点对里命中 4 次，和思路第 4 节手算的一致。只算轴平行的版本返回 1。 -- **m × m 网格点**，m 从 2 到 6（n 从 4 到 36）：网格里正方形个数有公式 Σ(m − k)²·k（k 从 1 到 m − 1，k 是正方形外接的轴平行方框边长），得 1、6、20、50、105，六个版本全部吻合。m = 7（n = 49）的 196 由除 O(n⁴) 外的五个版本核过。这个和化简后等于 n(n − 1)/12，m 从 2 到 60 核过。 -- **随机点集**：400 组，每组 4 到 12 个点取自 7 × 7 的范围，再往输入里塞 2 个重复点。以 O(n⁴) 版为标准答案，其余五个版本零不符（其中 30 组至少有一个正方形）。空列表、3 个点、同一个点的 6 个副本都返回 0。 -- **命中次数**：300 组随机点集上，O(n³) 版的命中数恒等于答案的 4 倍，O(n²) 对角线版恒等于 2 倍，边的版本恒等于 4 倍。 +代码都在 2026-10-24 用 Python 3.12.10 实际跑过（`python -I`）。另用一个脚本把本页每个 Python 代码块单独取出、在干净的命名空间里执行、用题目里的例子各调用一次，结果和下面一致。六个正确版本（$O(n^4)$ 枚举、$O(n^3)$ 对角线加第三点、$O(n^3)$ 任意三点、$O(n^2)$ 对角线乘 2、$O(n^2)$ 对角线判奇偶、$O(n^2)$ 边）放在同一组输入上比： + +- **题目里的例子**（6 个点）：六个版本都返回 2，$O(n^4)$ 版列出的两个正方形就是题目里写的那两个。15 个无序点对里命中 4 次，和思路第 4 节手算的一致。只算轴平行的版本返回 1。 +- **$m \times m$ 网格点**，m 从 2 到 6（n 从 4 到 36）：网格里正方形个数有公式 $\sum_{k=1}^{m-1} (m - k)^2 \cdot k$（k 是正方形外接的轴平行方框边长），得 1、6、20、50、105，六个版本全部吻合。m = 7（n = 49）的 196 由除 $O(n^4)$ 外的五个版本核过。这个和化简后等于 $n(n - 1)/12$，m 从 2 到 60 核过。 +- **随机点集**：400 组，每组 4 到 12 个点取自 $7 \times 7$ 的范围，再往输入里塞 2 个重复点。以 $O(n^4)$ 版为标准答案，其余五个版本零不符（其中 30 组至少有一个正方形）。空列表、3 个点、同一个点的 6 个副本都返回 0。 +- **命中次数**：300 组随机点集上，$O(n^3)$ 版的命中数恒等于答案的 4 倍，$O(n^2)$ 对角线版恒等于 2 倍，边的版本恒等于 4 倍。 - **错误版本和正确版本并排**： @@ -243,13 +250,13 @@ | 单位正方形 4 个点 | 1 | `// 2` 取整、不判奇偶 | 2 | | `[(0, 0), (1, 0), (1, 1), (2, 1)]` | 0 | `// 2` 取整、不判奇偶 | 1（(1, 0)–(1, 1) 的 2A = (1, 1)、2B = (3, 1) 取整成 (0, 0)、(1, 0)，假命中，(1, 1)–(2, 1) 那一对同理） | -| 菱形 `[(0, 0), (2, 1), (3, 3), (1, 2)]` | 0 | O(n³) 版只查等距、不查直角 | 1 | -| `[(0.1, 0.1), (0.2, 0.1), (0.2, 0.2), (0.1, 0.2)]` | 1 | 浮点数算中点、精确匹配 | 0（从对角线 (0.1, 0.1)–(0.2, 0.2) 算出的顶点是 (0.10000000000000002, 0.2)。先乘 10⁹ 取整再用整数做法，得 1） | -| (2⁵² + 2, 2⁵² + 2)、(2⁵² + 2, 2⁵² + 3)、(2⁵² + 2, 2⁵² + 4) 三个共线的整点 | 0 | 浮点数算中点、精确匹配 | 1（同样形状的三个点放在 2⁵¹ + 2 或原点附近，答 0。3 × 3 的整点窗口最大坐标是 2⁵² − 1 时，全部 3 点、4 点子集都答对，窗口跨过 2⁵² 就有 3 个子集答错） | +| 菱形 `[(0, 0), (2, 1), (3, 3), (1, 2)]` | 0 | $O(n^3)$ 版只查等距、不查直角 | 1 | +| `[(0.1, 0.1), (0.2, 0.1), (0.2, 0.2), (0.1, 0.2)]` | 1 | 浮点数算中点、精确匹配 | 0（从对角线 (0.1, 0.1)–(0.2, 0.2) 算出的顶点是 (0.10000000000000002, 0.2)。先乘 $10^9$ 取整再用整数做法，得 1） | +| $(2^{52} + 2, 2^{52} + 2)$、$(2^{52} + 2, 2^{52} + 3)$、$(2^{52} + 2, 2^{52} + 4)$ 三个共线的整点 | 0 | 浮点数算中点、精确匹配 | 1（同样形状的三个点放在 $2^{51} + 2$ 或原点附近，答 0。$3 \times 3$ 的整点窗口最大坐标是 $2^{52} - 1$ 时，全部 3 点、4 点子集都答对，窗口跨过 $2^{52}$ 就有 3 个子集答错） | - **奇偶性**：x、y 在 −6 到 6 之间的全部 28561 组点对，2A、2B 的四个坐标奇偶性都相同，零例外。 -- **Follow-up 第 1 条**：只算轴平行的版本和按定义穷举的结果在 500 组随机点集上零不符。4 × 4 网格轴平行的有 14 个，全部正方形 20 个。 -- **Follow-up 第 3 条**：重复点分别算的版本和「把每个副本当成不同的点、穷举 4 个点」的结果在 300 组随机输入上零不符。单位正方形多一个 (0, 0) 的副本得 2（两个 (0, 0) 各配一次），每个顶点都给两份得 2⁴ = 16。 +- **Follow-up 第 1 条**：只算轴平行的版本和按定义穷举的结果在 500 组随机点集上零不符。$4 \times 4$ 网格轴平行的有 14 个，全部正方形 20 个。 +- **Follow-up 第 3 条**：重复点分别算的版本和「把每个副本当成不同的点、穷举 4 个点」的结果在 300 组随机输入上零不符。单位正方形多一个 (0, 0) 的副本得 2（两个 (0, 0) 各配一次），每个顶点都给两份得 $2^4 = 16$。 - **Follow-up 第 4 条**：LeetCode 2013 的官方例子（加 (3, 10)、(11, 2)、(3, 2) 后查 (11, 10) 得 1，查 (14, 8) 得 0，再加一次 (11, 2) 后查 (11, 10) 得 2）通过。 -- **计时**（随机整点，n = 40、80 从 30 × 30 的网格里取，n = 400、2000 从 100 × 100 里取。「—」表示太慢、没跑）： +- **计时**（随机整点，n = 40、80 从 $30 \times 30$ 的网格里取，n = 400、2000 从 $100 \times 100$ 里取。「—」表示太慢、没跑）： | 版本 | n = 40 | n = 80 | n = 400 | n = 2000 | @@ -264,5 +271,5 @@ ### 1. 只算和坐标轴平行的正方形 -轴平行的正方形，对角线的两个端点横坐标之差和纵坐标之差绝对值相等（|dx| = |dy|，且不为 0），另两个顶点就是 (x1, y2) 和 (x2, y1)，不用转 90° 也不用乘 2。在第 4 节的循环里加这一个过滤就行： +轴平行的正方形，对角线的两个端点横坐标之差和纵坐标之差绝对值相等（$|dx| = |dy|$，且不为 0），另两个顶点就是 $(x_1, y_2)$ 和 $(x_2, y_1)$，不用转 90° 也不用乘 2。在第 4 节的循环里加这一个过滤就行： ```python @@ -282,5 +289,5 @@ ``` -这个过滤是对的，因为轴平行正方形的四个顶点是 (x1, y1)、(x2, y1)、(x2, y2)、(x1, y2)，对角线端点 (x1, y1)、(x2, y2) 必有 |x2 − x1| = |y2 − y1|。反过来满足这个条件、另两个角也在，就是一个边长 |dx| 的轴平行正方形。还是每个正方形两条对角线，除以 2。复杂度不变，仍是 O(n²)，只是过滤掉了大部分点对的查找。 +这个过滤是对的，因为轴平行正方形的四个顶点是 $(x_1, y_1)$、$(x_2, y_1)$、$(x_2, y_2)$、$(x_1, y_2)$，对角线端点 $(x_1, y_1)$、$(x_2, y_2)$ 必有 $|x_2 - x_1| = |y_2 - y_1|$。反过来满足这个条件、另两个角也在，就是一个边长 $|dx|$ 的轴平行正方形。还是每个正方形两条对角线，除以 2。复杂度不变，仍是 $O(n^2)$，只是过滤掉了大部分点对的查找。 ### 2. 坐标是浮点数 @@ -288,13 +295,13 @@ 整数做法靠的是「算出来的顶点和输入里的点精确相等」。坐标是小数时这个前提就没了：0.1 + 0.2 在浮点数里是 0.30000000000000004，从对角线 (0.1, 0.1)–(0.2, 0.2) 算出来的顶点和集合里的 (0.1, 0.2) 差在最后一位，对不上，一个明明存在的正方形会数成 0（测试用例的错误版本表）。 -处理办法是先把坐标对齐到一个网格：确认坐标的精度（比如小数点后 6 位），把每个坐标乘 10⁶ 后 `round` 成整数，之后全部用整数做法。这样「相等」就是整数相等，没有误差。代价是精度之内的两个点会被当成同一个点，这正是要和面试官确认的：输入保证多少位精度。 - -如果面试官说坐标是任意实数、不保证精度，就只能比「坐标差的绝对值不超过容差（tolerance）ε」。ε 要比计算误差大：double 每一步运算的相对误差不超过 2⁻⁵³（约 1.1 × 10⁻¹⁶），算一个顶点要三四步，误差是坐标绝对值的几倍 10⁻¹⁶。它又要比两个本该不同的点之间的最小距离小，不然相邻的真实点会被当成同一个点。这两头夹出的范围要和面试官确认。哈希集合做不了容差比较（两个只差一点点的浮点数哈希值完全不同），要换成网格分桶：桶的边长取 ε，点 (x, y) 放进编号为 (⌊x/ε⌋, ⌊y/ε⌋) 的桶。和算出的顶点每个坐标相差不超过 ε 的点，桶编号每一维最多差 1，所以一定在顶点所在的桶或周围 8 个桶里，只看这 9 个桶、逐个比坐标差就不会漏。每次查找的代价是这 9 个桶里的点数：点分布稀疏时是常数，大量点挤在几个 ε 的范围内时退化成 O(n)。 - -坐标是整数、但用浮点数算中点，坐标很大时也会错。double 有 53 位有效数字：绝对值小于 2⁵² 的数，相邻两个 double 相差不超过 0.5，半整数都能精确表示。2⁵² 到 2⁵³（约 4.5 × 10¹⁵ 到 9 × 10¹⁵）之间，相邻两个 double 相差 1，只能表示整数。所有坐标的绝对值都小于 2⁵² 时，两个坐标之和小于 2⁵³、是精确的整数，除以 2、再加减半条对角线，结果只要还在 ±2⁵² 以内就是精确的整数或半整数。超出 ±2⁵² 的顶点，舍入后仍在 ±2⁵² 以外，本来就不可能等于输入里的点，所以不会错。一旦有坐标到了 2⁵² 以上，算出的半整数顶点会被舍入成整数，正好撞上真实点就是假命中，三个共线的点也能数出一个正方形（例子在测试用例的错误版本表里）。整数做法没有除法，不受这个限制。 +处理办法是先把坐标对齐到一个网格：确认坐标的精度（比如小数点后 6 位），把每个坐标乘 $10^6$ 后 `round` 成整数，之后全部用整数做法。这样「相等」就是整数相等，没有误差。代价是精度之内的两个点会被当成同一个点，这正是要和面试官确认的：输入保证多少位精度。 + +如果面试官说坐标是任意实数、不保证精度，就只能比「坐标差的绝对值不超过容差（tolerance）ε」。ε 要比计算误差大：double 每一步运算的相对误差不超过 $2^{-53}$（约 $1.1 \times 10^{-16}$），算一个顶点要三四步，误差是坐标绝对值的几倍 $10^{-16}$。它又要比两个本该不同的点之间的最小距离小，不然相邻的真实点会被当成同一个点。这两头夹出的范围要和面试官确认。哈希集合做不了容差比较（两个只差一点点的浮点数哈希值完全不同），要换成网格分桶：桶的边长取 ε，点 $(x, y)$ 放进编号为 $(\lfloor x/\varepsilon \rfloor, \lfloor y/\varepsilon \rfloor)$ 的桶。和算出的顶点每个坐标相差不超过 ε 的点，桶编号每一维最多差 1，所以一定在顶点所在的桶或周围 8 个桶里，只看这 9 个桶、逐个比坐标差就不会漏。每次查找的代价是这 9 个桶里的点数：点分布稀疏时是常数，大量点挤在几个 ε 的范围内时退化成 $O(n)$。 + +坐标是整数、但用浮点数算中点，坐标很大时也会错。double 有 53 位有效数字：绝对值小于 $2^{52}$ 的数，相邻两个 double 相差不超过 0.5，半整数都能精确表示。$2^{52}$ 到 $2^{53}$（约 $4.5 \times 10^{15}$ 到 $9 \times 10^{15}$）之间，相邻两个 double 相差 1，只能表示整数。所有坐标的绝对值都小于 $2^{52}$ 时，两个坐标之和小于 $2^{53}$、是精确的整数，除以 2、再加减半条对角线，结果只要还在 $\pm 2^{52}$ 以内就是精确的整数或半整数。超出 $\pm 2^{52}$ 的顶点，舍入后仍在 $\pm 2^{52}$ 以外，本来就不可能等于输入里的点，所以不会错。一旦有坐标到了 $2^{52}$ 以上，算出的半整数顶点会被舍入成整数，正好撞上真实点就是假命中，三个共线的点也能数出一个正方形（例子在测试用例的错误版本表里）。整数做法没有除法，不受这个限制。 ### 3. 重复的点要分别算 -如果面试官说输入里同一个位置可以出现多次、而且每一份都算不同的点，那么「一个正方形」就要按选法数：四个位置各出现 c1、c2、c3、c4 次，这四个位置能组成 c1 × c2 × c3 × c4 个不同的正方形。做法是用 `Counter` 记每个位置出现几次，枚举两个不同位置当对角线，把四个位置的次数相乘累加，最后仍然除以 2： +如果面试官说输入里同一个位置可以出现多次、而且每一份都算不同的点，那么「一个正方形」就要按选法数：四个位置各出现 $c_1$、$c_2$、$c_3$、$c_4$ 次，这四个位置能组成 $c_1 \times c_2 \times c_3 \times c_4$ 个不同的正方形。做法是用 `Counter` 记每个位置出现几次，枚举两个不同位置当对角线，把四个位置的次数相乘累加，最后仍然除以 2： ```python @@ -314,5 +321,5 @@ ``` -这个做法是对的，因为四个位置组成的每个正方形还是会被它的两条对角线各找到一次，两次算出的乘积都是 c1 × c2 × c3 × c4，所以总和是答案的 2 倍，除以 2 正好。缺哪个顶点，`get` 返回 0，乘积就是 0。重合的点不会被当成边长为 0 的正方形，因为枚举的是两个不同的位置。 +这个做法是对的，因为四个位置组成的每个正方形还是会被它的两条对角线各找到一次，两次算出的乘积都是 $c_1 \times c_2 \times c_3 \times c_4$，所以总和是答案的 2 倍，除以 2 正好。缺哪个顶点，`get` 返回 0，乘积就是 0。重合的点不会被当成边长为 0 的正方形，因为枚举的是两个不同的位置。 ### 4. 点是动态加进来的，查「含某个点的正方形有几个」 @@ -320,5 +327,5 @@ 这是 LeetCode 2013 Detect Squares 的形式：有 `add(point)` 和 `count(point)` 两个操作，`count` 问以这个点为一个顶点、另外三个顶点都已经加进来的正方形有几个，同一个坐标可以加多次、按次数算。LeetCode 上只算轴平行的。 -做法还是把查询点 (x1, y1) 当对角线的一端：遍历所有已加入的点当另一端 (x2, y2)，记 dx = x2 − x1、dy = y2 − y1，要求 |dx| = |dy| 且不为 0，另两个角是 (x1, y2) 和 (x2, y1)，三个点的出现次数相乘累加。每次查询 O(n)，加点 O(1)。这里不用除，因为查询点固定，每个正方形只在「它的对角顶点」那一轮被数一次。 +做法还是把查询点 $(x_1, y_1)$ 当对角线的一端：遍历所有已加入的点当另一端 $(x_2, y_2)$，记 $dx = x_2 - x_1$、$dy = y_2 - y_1$，要求 $|dx| = |dy|$ 且不为 0，另两个角是 $(x_1, y_2)$ 和 $(x_2, y_1)$，三个点的出现次数相乘累加。每次查询 $O(n)$，加点 $O(1)$。这里不用除，因为查询点固定，每个正方形只在「它的对角顶点」那一轮被数一次。 ```python @@ -341,13 +348,13 @@ ``` -如果面试官要斜的也算，遍历时先跳过和查询点同一个位置的点：查询点自己也可能已经加进来过，它和自己组成长度为 0 的「对角线」，算出的两个角都是查询点本身，会凭空多数。其余的点把条件换成第 4 节的公式（sx = x1 + x2、sy = y1 + y2，dx、dy 同上）：sx − dy 是奇数就跳过，否则另两个角是 ((sx − dy)/2, (sy + dx)/2) 和 ((sx + dy)/2, (sy − dx)/2)，同样三个次数相乘。 +如果面试官要斜的也算，遍历时先跳过和查询点同一个位置的点：查询点自己也可能已经加进来过，它和自己组成长度为 0 的「对角线」，算出的两个角都是查询点本身，会凭空多数。其余的点把条件换成第 4 节的公式（$sx = x_1 + x_2$、$sy = y_1 + y_2$，dx、dy 同上）：$sx - dy$ 是奇数就跳过，否则另两个角是 $\left(\frac{sx - dy}{2}, \frac{sy + dx}{2}\right)$ 和 $\left(\frac{sx + dy}{2}, \frac{sy - dx}{2}\right)$，同样三个次数相乘。 ### 5. 能不能比 O(n²) 更快 -先说答案的规模：m × m 的网格点一共 n = m² 个，其中的正方形恰好有 n(n − 1)/12 个（测试用例里网格公式化简的结果），和 n² 同阶。任何「把每个正方形都找出来一次」的算法，输出就有 n² 量级，不可能快过 O(n²)。只算总数、不逐个找的算法理论上不受这个限制，但没有查到实用的做法【未核实】。面经里的追问也都止于 O(n²)。 +先说答案的规模：$m \times m$ 的网格点一共 $n = m^2$ 个，其中的正方形恰好有 $n(n - 1)/12$ 个（测试用例里网格公式化简的结果），和 $n^2$ 同阶。任何「把每个正方形都找出来一次」的算法，输出就有 $n^2$ 量级，不可能快过 $O(n^2)$。只算总数、不逐个找的算法理论上不受这个限制，但没有查到实用的做法【未核实】。面经里的追问也都止于 $O(n^2)$。 ### 6. 不让用哈希集合 -面试官有时会问「不用哈希表怎么办」。把去重后的点排序存进列表，「查一个点在不在」就变成二分查找（`bisect`），每次 O(log n)，三级的复杂度分别变成 O(n⁴)（不查找，不变）、O(n³ log n)、O(n² log n)。做法本身一个字不改，只是「算出来的点」从 O(1) 查到变成 O(log n) 查到。没有一篇面经记下面试官要求过这一条。 +面试官有时会问「不用哈希表怎么办」。把去重后的点排序存进列表，「查一个点在不在」就变成二分查找（`bisect`），每次 $O(\log n)$，三级的复杂度分别变成 $O(n^4)$（不查找，不变）、$O(n^3 \log n)$、$O(n^2 \log n)$。做法本身一个字不改，只是「算出来的点」从 $O(1)$ 查到变成 $O(\log n)$ 查到。没有一篇面经记下面试官要求过这一条。 ## 英文讲法
meta
@@ -1,5 +1,5 @@ { "depth_guide": "2026-10-23", - "rewritten_by": "local", - "rewritten_at": "2026-10-25" + "rewritten_by": "cloud:20261026-2311", + "rewritten_at": "2026-10-27" }