用哈希表高效统计平行四边形数量：中点+方向向量法

1. 代码讲解在讨论“平行四边形数量”这个题目时最核心的引导性问题就是如何用数据结构来计数而不是用暴力几何直接数。我见过很多同学一拿到这个题第一反应就是枚举四个点然后判断两两对边是否平行且相等或者用向量叉积判断是否共线。这种思路没错但放在大规模坐标点下根本跑不动。先说清楚我处理这类统计题目的通用套路把几何性质映射到数据结构能处理的“键值对”上然后利用哈希表或排序去重完成计数。这也是LeetCode、牛客上很多“几何计数类”题目的通用解法。这道题的核心观察是在一个平面坐标系中给出一组点如果两条线段的中点相同且这两条线段不共线也就是它们不是同一条直线上的重叠或延伸那么这两条线段的四个端点一定能构成一个平行四边形。为什么你可以把平行四边形的两条对角线拿出来看它们的交点正是两条对角线的共同中点。反过来任意两条“中点相同”且“不共线”的线段恰好可以作为一个平行四边形的两条对角线四个端点围成的图形必然满足对边平行且相等。用生活化的类比来说你有一堆木棍每条木棍有自己的中心点。你把所有中心点相同的木棍分成一组。这一组里任意挑两根木棍它们四个端点就是平行四边形的四个顶点。关键在于“任意挑两根”这就变成了组合数 C(n, 2) n * (n-1) / 2 的问题。那么数据结构就派上用场了——我们需要一个能够快速计算“相同中点”出现次数的结构。思路如下遍历所有点对计算它们的中点坐标以“中点坐标”作为键存到一个哈希表里每次向哈希表插入一个新点对时如果这个中点已经出现过 k 次那么新插入的点对就能和之前 k 个点对分别构成 k 个新的平行四边形累计所有插入时的 k 值就是最终答案。这个算法的时间复杂度是 O(n^2)空间复杂度也是 O(n^2)其中 n 是点的数量。为什么不能更优因为任何算法在最坏情况下都需要枚举点对而点对本身就有 O(n^2) 个。所以 O(n^2) 是这个问题的理论下界哈希表的做法已经是最优的实用方案。这还没完。很多人会忽略一个细节如果两条线段的中点相同但它们在同一条直线上那么这四个点构成的是退化的平行四边形也就是四点共线不应该计入答案。比如点 (0,0)、(1,1)、(2,2)、(3,3)任意两条线段的中点都可能相同但它们根本围不成平行四边形。所以在插入哈希表时我们必须把“方向”也纳入判断。怎么判断两条线段是否在同一条直线上最简单的做法是对每一条线段除了计算中点还要记录它的斜率或者方向向量的标准化形式。具体来说我们可以将线段的向量 (dx, dy) 化为最简分数形式例如 (dx/g, dy/g)其中 g 是 dx 和 dy 的最大公约数同时保证 dx 的符号一致比如规定 dx 0如果 dx 0 则规定 dy 0。这个标准化后的向量就是该线段的方向。如果两个线段中点相同且方向相同说明它们在同一条直线上不能构成平行四边形如果中点相同但方向不同则可以构成平行四边形。因此哈希表的键不能只是“中点坐标”而应该是“(中点坐标, 方向向量)”的二元组。每一组内点对之间才真正可以两两组合形成平行四边形。我把完整思路先用伪代码写出来from collections import defaultdict from math import gcd def count_parallelograms(points): # 键: (mx, my, vx, vy), 值: 该中点方向下的线段数量 count_map defaultdict(int) ans 0 for i in range(len(points)): for j in range(i 1, len(points)): x1, y1 points[i] x2, y2 points[j] # 中点坐标 mx x1 x2 my y1 y2 # 方向向量标准化 dx x2 - x1 dy y2 - y1 g gcd(abs(dx), abs(dy)) dx // g dy // g if dx 0 or (dx 0 and dy 0): dx -dx dy -dy # 组内已有线段数就是新增平行四边形数 key (mx, my, dx, dy) ans count_map[key] count_map[key] 1 return ans这里有一个容易踩坑的细节中点坐标为什么要存储x1 x2而不是(x1 x2) / 2因为整数加法不会产生浮点误差而浮点除法可能因为精度问题导致两个本应相等的键不相等。在实际比赛或面试中这种细节往往决定了代码能否一次通过。坐标范围较大时直接存两倍中点坐标完全可行因为两个点对的中点相同当且仅当它们的坐标和相同。另外在 C 或 Java 里你可以用mappairpairint,int, pairint,int, int做同样的事但 Python 的tuple直接哈希更省事。若坐标值可能很大注意用 long long 或 int64 存储x1 x2防止溢出。举个例子验证一下给定四个点 (0,0)、(1,0)、(0,1)、(1,1)它们正好是一个正方形的四个顶点。按代码跑一遍点对 (0,0)-(1,0)中点 (1,0)方向 (1,0)点对 (0,1)-(1,1)中点 (1,1)方向 (1,0)点对 (0,0)-(0,1)中点 (0,1)方向 (0,1)点对 (1,0)-(1,1)中点 (2,1)方向 (0,1)点对 (0,0)-(1,1)中点 (1,1)方向 (1,1)点对 (1,0)-(0,1)中点 (1,1)方向 (-1,1)标准化后仍是 (-1,1)因为 dx 0符号不变注意点对 (0,0)-(1,1) 和 (1,0)-(0,1) 中点相同但方向分别是 (1,1) 和 (-1,1)不同所以它们构成一个平行四边形——正是这个正方形本身。而点对 (0,1)-(1,1) 和 (0,0)-(0,1) 中点不同不会误判。最终 ans 累计为 1正确。2. 算法复杂度与优化上面的哈希表做法是 O(n^2) 的这在 n ≤ 2000 时大约要跑 200 万次点对枚举单次操作主要是哈希表的插入与查询Python 实测不到 1 秒n ≤ 5000 时约 1250 万次Python 可能需要几秒C 则毫无压力n ≤ 100000 时O(n^2) 基本不可能完成必须另寻他路。那有没有更优的算法我直接说结论在一般性的平面点集上统计平行四边形数量的最优时间复杂度就是 O(n^2)。原因很简单点对数量本身就是 O(n^2) 的量级任何算法想要不遗漏候选线段对就必须访问或生成所有点对信息。哈希表的常数虽然不小但在 O(n^2) 范围内已经是最实用的方案。不过有几种特殊情况可以优化点集存在大量重合点或共线点这反而可能让哈希表分组更多但总枚举量不变。如果题目保证没有三点共线那连“同向判断”都可以省掉代码更简单。如果只需要数量不需要输出具体哪些点哈希表做法是最合适的如果需要输出具体平行四边形就必须额外存每组内的线段端点列表。坐标范围有限且较小比如 0 ≤ x, y ≤ 100可以考虑用二维数组代替哈希表将中点坐标映射到数组下标方向用四元组索引这样查询和插入都是 O(1) 且常数极小。n 特别大但坐标点稀疏时可以先用坐标离散化或基于空间索引如 KD 树剪枝但这属于工程优化竞赛和面试一般用不到。如果在面试中遇到这道题我建议你先把哈希表思路讲清楚再补充说明“中点相同 方向不同”是判定平行四边形的充要条件最后用一个小例子走一遍流程。面试官一般会满意因为这是公认的最优解法。3. 常见问题与排查技巧3.1 浮点数精度问题这是最常见的坑。很多人写mid ((x1x2)/2, (y1y2)/2)然后拿 float 当字典键。坐标是整数时中点可能带 0.5浮点表示在绝大多数情况下是精确的因为 0.5 是 2 的负幂次但如果坐标是浮点数或者运算更复杂就可能出现0.1 0.2 ! 0.3的情况。应对方法是能不用浮点就不用浮点。整数坐标一律存坐标和浮点坐标则考虑乘以一个足够大的缩放因子转成整数或者用Fraction分数类但性能较差。3.2 共线导致的退化平行四边形如果两条线段中点相同且方向相同它们位于同一条直线上四个端点共线不能构成平行四边形。我们需要在键中加入方向向量来区分。方向向量标准化的目的是为了让 (1,1) 和 (2,2) 被视为同一方向。如果不做标准化同一条直线的不同长度的线段会被当成不同方向导致计数错误。标准化还有个好处是方便比较方向是否相同。注意符号统一规则我习惯规定标准化后的 dx 必须为正若 dx 为 0则 dy 必须为正。这样可以保证方向向量 (dx, dy) 与 (-dx, -dy) 被认为是同一个方向因为线段是无向的。3.3 重复点问题如果输入点集中存在完全相同的点情况会变得复杂。比如点 (0,0) 出现了两次那么点对 ((0,0), (1,1)) 与 ((0,0), (1,1)) 虽然是不同的“索引点对”但它们在几何上是同一条线段的两条“实例”。那它们能构成平行四边形吗答案是不能因为四个端点实际上只有三个不同的位置两个 (0,0) 重合无法围成真正的平行四边形。处理方法是在统计前先去重。用集合set(points)去掉重复点再跑算法。如果题目明确允许重复点并另有定义那就需要按题面特殊处理但大多数情况下去重是正确且安全的。3.4 整数溢出在 C 中x1 x2可能超出 int 范围。比如坐标范围是 [-10^9, 10^9]两个坐标和可能达到 210^9int 上限是 2.14710^9正好擦边但如果你还做乘法或累加很容易溢出。稳妥做法是统一用long long。Python 则无需担心。3.5 方向向量计算中的除零当点对的两个点相同dx0, dy0时gcd(0,0) 未定义。我们在去重后这种情况就不会出现。但如果没去重而出现相同点最好先排除掉i ! j时坐标也完全相等的情况否则方向向量的标准化会出错。3.6 答案数量超过 int 范围考虑 n2000 的点集若大量中点相同答案可能达到上亿级别。例如所有点分布在两个平行直线上每组内线段数量可能很大。最好用 64 位整数存储答案。我在实际做题时经常看到有人用 int 存 ans结果 WA 了还不知道为什么。排查方法很简单在本地造一个极端的随机点集对比 int 与 long long 的输出立刻就能发现问题。4. 题目变体与扩展思路“平行四边形数量”这类几何计数题在面试和竞赛里有一堆变体核心还是“几何性质 → 数据结构”的映射思路我梳理几个常见的4.1 统计矩形数量矩形是特殊的平行四边形。除了满足对角线中点相同还要求两条对角线长度相等。所以哈希表的键变成了“(中点坐标, 对角线长度)”组内两两组合。这就是 LeetCode 上“检测矩形”类题目的通用思路。延伸到正方形则还要再加一个条件两条对角线长度相等且互相垂直。4.2 统计三角形数量给定点集统计能组成三角形的个数。思路是先算总组合数 C(n,3)再减去三点共线的组合数。三点共线的判断可以固定一个点对其余点按斜率排序或哈希分组复杂度可以做到 O(n^2 log n) 或 O(n^2)。这类题目在拓扑学或计算几何中很常见。4.3 统计平行四边形是否为菱形菱形要求对角线互相垂直。在已知中点相同的前提下只需再比较两条线段的方向向量点积是否为 0。也就是说哈希表键可以扩展为更复杂的结构但整体框架不变。这提醒我们几何计数题的本质是把复杂几何条件拆解成若干可哈希的简单属性的组合。4.4 针对大规模点集的近似解法当 n 达到十万级别精确 O(n^2) 不可行。这时可以根据应用场景用随机采样、桶分块、或基于GPU的并行枚举来近似。但对数据结构考试或面试而言O(n^2) 的哈希表解法已经足够。5. 完整可运行代码示例为了让这篇博客真正“可抄作业”我给出 Python 和 C 两个版本的完整实现。两个版本均包含注释和边界情况处理。5.1 Python版本from collections import defaultdict from math import gcd def count_parallelograms(points): 计算平面点集中能构成平行四边形的数量。 参数 points: List[Tuple[int, int]]坐标均为整数。 返回: int平行四边形数量。 # 第一步去重避免重复点带来的退化情况 pts list(set(points)) n len(pts) # count_map 的键为 (mx, my, dx, dy) # 其中 (mx, my) 是线段中点坐标的两倍用和代替 # (dx, dy) 是标准化后的方向向量 count_map defaultdict(int) ans 0 for i in range(n): x1, y1 pts[i] for j in range(i 1, n): x2, y2 pts[j] mx x1 x2 my y1 y2 dx x2 - x1 dy y2 - y1 # 标准化方向向量 g gcd(abs(dx), abs(dy)) dx // g dy // g # 符号统一确保 dx 0若 dx 0 则确保 dy 0 if dx 0 or (dx 0 and dy 0): dx -dx dy -dy key (mx, my, dx, dy) ans count_map[key] count_map[key] 1 return ans # 测试用例 if __name__ __main__: # 正方形 pts1 [(0, 0), (1, 0), (0, 1), (1, 1)] print(count_parallelograms(pts1)) # 预期 1 # 两个正方形共享一条边 pts2 [(0, 0), (2, 0), (1, 1), (0, 2), (2, 2), (1, 3)] print(count_parallelograms(pts2)) # 预期 2 # 重复点情况 pts3 [(0, 0), (0, 0), (1, 0), (0, 1), (1, 1)] print(count_parallelograms(pts3)) # 去重后同 pts1预期 15.2 C 版本#include bits/stdc.h using namespace std; struct Point { int x, y; bool operator(const Point other) const { if (x ! other.x) return x other.x; return y other.y; } }; long long countParallelograms(vectorPoint input) { // 去重 setPoint s(input.begin(), input.end()); vectorPoint pts(s.begin(), s.end()); int n pts.size(); // 键为 (mx, my, dx, dy) maptupleint, int, int, int, int mp; long long ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { int mx pts[i].x pts[j].x; int my pts[i].y pts[j].y; int dx pts[j].x - pts[i].x; int dy pts[j].y - pts[i].y; int g gcd(abs(dx), abs(dy)); dx / g; dy / g; if (dx 0 || (dx 0 dy 0)) { dx -dx; dy -dy; } auto key make_tuple(mx, my, dx, dy); ans mp[key]; mp[key]; } } return ans; } int main() { vectorPoint pts1 {{0, 0}, {1, 0}, {0, 1}, {1, 1}}; cout countParallelograms(pts1) endl; // 预期 1 vectorPoint pts2 {{0, 0}, {2, 0}, {1, 1}, {0, 2}, {2, 2}, {1, 3}}; cout countParallelograms(pts2) endl; // 预期 2 return 0; }如果你在本地运行测试建议再构造一组随机点用暴力 O(n^4) 枚举法对照验证哈希表算法是否正确。暴力法虽然慢但在小数据量下是验证正确性的利器。我把暴力验证的思路也贴出来def brute_force(points): pts list(set(points)) n len(pts) ans 0 for a in range(n): for b in range(a 1, n): for c in range(b 1, n): for d in range(c 1, n): p1, p2, p3, p4 pts[a], pts[b], pts[c], pts[d] # 判断是否构成平行四边形两组对边中点相同即成立 if p1[0] p2[0] p3[0] p4[0] and p1[1] p2[1] p3[1] p4[1]: ans 1 elif p1[0] p3[0] p2[0] p4[0] and p1[1] p3[1] p2[1] p4[1]: ans 1 elif p1[0] p4[0] p2[0] p3[0] and p1[1] p4[1] p2[1] p3[1]: ans 1 return ans这里用到的判定是如果四边形 ABCD 中AC 和 BD 的中点相同那么 ABDC 构成平行四边形顶点顺序可能不同。实际计算中枚举四个点的任意三种配对方式只要有一种满足中点相同即可。注意这种暴力法没有排除共线退化情况所以在测试时会比正式算法多算一些共线四点。要想严格对照可以在暴力法里也加入方向判断或者确保测试数据中没有四点共线。这也是一个容易让人困惑的细节如果暴力验证代码和正式算法不完全等价你会得到对不上的结果然后白白排查半天。6. 一题多解不同数据规模下的方案选择最后再展开聊一下如果题目换一个数据范围解法该如何调整。这道题在不同平台上出现过多种变体数据范围从小到大都有方案选择完全不同数据规模推荐方案时间复杂度说明n ≤ 50四重循环暴力枚举O(n^4)用中点判定代码最简单n ≤ 5000哈希表 方向标准化O(n^2)这是本文主推做法足够快n ≤ 10^5近似算法 / 并行优化视情况而定精确解没有多项式优化空间只能靠工程手段对于 n ≤ 50 的小数据暴力枚举甚至不需要哈希表直接四重循环计算中点是否成对相等即可。但即使数据小我也建议用哈希表写法练手因为代码量的增加微乎其微却能让你更熟悉“几何映射到哈希表”的套路。到了 n ≤ 5000 时C 哈希表轻松搞定Python 稍作优化比如用defaultdict而不是dict手动判断也没有问题。在实际竞赛中还有一种常见做法是用“中点 方向”的组合直接排序后统计不做哈希。排序后相同键的项会连续排列然后对每一段相同键做组合数累加。这种做法的复杂度是 O(n^2 log n)比哈希表稍慢但好处是代码更直观并且更容易扩展成输出具体平行四边形的逻辑。比如你需要列出所有平行四边形的顶点那就在排序后的同一组内枚举所有点对组合即可。如果还想再快一点可以做一个小优化把点的坐标离散化到更小的编号然后用二维数组存储“中点出现次数”。但这要求坐标范围本身不大否则数组开不下。哈希表在大多数情况下已经够用属于“性价比最高”的方案。我个人在实际刷题中用得最多的还是 Python 的defaultdict配合元组做键代码量很少而且不易出错。C 版本则要注意tuple在map中的使用C17 之后map对tuple有天然支持比较方便。如果你在面试中被问到这道题还有一个小技巧在讲完哈希表解法后主动补充一句“如果题目允许点集存在共线点需要额外用方向向量区分退化情况”这会让面试官觉得你考虑问题很全面。面试官如果追问“为什么哈希表键里要存中点的两倍而不是除以 2”你只要回答“为了避免浮点精度问题”基本就过关了。以上是整个平行四边形计数问题的完整解析。这道题看似简单实则把“几何性质 ↔ 数据结构 ↔ 计数模型”三者结合得非常紧密。如果只是记住哈希表解法而不理解“对角线中点相同”这个几何条件换一个题目比如数矩形、数菱形仍然会无从下手。理解原理之后不管题面怎么变你都能迅速找到对应的数据结构解法。