看到【数据结构】平行四边形数量这个标题我第一反应是这又是一道经典的“披着几何外衣”的数据结构题。很多人在期末考试、考研数据结构真题、或者面试算法题里都遇到过它题目描述通常只有一句话给定平面上 n 个点求这 n 个点能组成多少个平行四边形。别小看这句话它背后把哈希表、集合映射、组合计数、浮点数精度处理这些数据结构核心知识全串起来了是一道非常典型的“以数据结构为主、以几何性质为辅”的综合题。这篇文章我打算直接以一个刷题过来人的视角把这道题的完整思路、代码实现、复杂度分析、踩坑实录全部拆开来讲。无论是正在准备考研数据结构、还是在刷算法面试题、又或者是期末复习想找一道题吃透哈希表的用法这篇文章应该都能让你有收获。我会从数学性质讲到哈希函数设计从 C 代码讲到 Python 实现尽量做到看完就能自己写出来。1. 一个看似几何的题为什么会被归到数据结构1.1 题目到底在问什么先确认一下题面。给定 n 个二维平面上的点点的坐标都是整数要求统计由这些点作为四个顶点能组成多少个平行四边形。注意这里说的是“不同的平行四边形”而不是“不同的顶点组合”所以如果四个点确定一个平行四边形它只能被计数一次。第一次看到这类题很多人会误以为要用计算几何的模板比如极角排序、向量叉积、直线扫描之类。但细想一下会发现计算几何在这道题里只是“背景设定”真正决定复杂度上限的是你怎么对这些点做组织和检索。也就是说这道题考察的核心是数据结构怎么存、怎么查、怎么避免重复计数。我在实际刷题群里见过不少同学一看到“平面点集”就往凸包、旋转卡壳那个方向想结果越写越复杂。其实这道题最优雅的解法只需要一个非常朴素的性质平行四边形两条对角线互相平分。1.2 换个角度看中点从几何性质到数据结构设计平行四边形的判定有很多种比如两组对边分别平行、一组对边平行且相等、对角线互相平分等等。在这道题里最合适的是“对角线互相平分”。为什么因为“判断两条线段的中点是否相同”这件事在整数坐标下可以非常精确地完成。设平行四边形的四个顶点是 A、B、C、D其中 A 和 C 是一条对角线的两个端点B 和 D 是另一条对角线的两个端点那么必然满足(A.x C.x, A.y C.y) (B.x D.x, B.y D.y)也就是两条对角线的中点坐标相同。这个性质一旦转化为“若干对点的中点是否相同”问题就立刻从几何领域切换到了数据结构领域我们需要枚举所有点对计算每一个点对的中点然后统计“具有相同中点的点对有多少个”。如果某个中点出现了 k 次那么从这个中点出发任意两条不同的点对都能组成一个平行四边形因此贡献的组合数为 C(k, 2) k * (k - 1) / 2。到了这一步这道题的核心就完全变成了如何快速统计大量键值中点的出现次数。哈希表就是这个场景下的最优选择。2. 核心算法思路枚举点对 哈希表统计中点2.1 暴力枚举为什么不可行先看最直观的暴力做法从 n 个点里选 4 个不同点然后判断这 4 个点能否组成平行四边形。选 4 个点一共有 C(n, 4) 种组合判断一次需要检查对角线是否互相平分所以整体复杂度是 O(n^4)。当 n 100 时C(100, 4) 大约是 390 万勉强能跑当 n 500 时C(500, 4) 大约是 26 亿直接爆炸当 n 2000 时这个数字是 6.6 万亿等你跑完比赛都结束了。我在面试时见过有候选人提出用回溯法枚举四个点再剪枝这思路本身没错但剪枝条件在这个场景下很难设计因为平行四边形没有“方向性”你提前排掉一个点可能就把正确答案排掉了。所以 O(n^4) 的暴力方案基本只适合作为面试开场白绝对不适合作为最终答案。2.2 两条对角线的性质如何变成 O(n²) 的优雅解优化的突破口在于不要枚举“四个点”而是枚举“两条对角线”。任意两条不同的线段如果它们的中点相同且不共端点那么这两条线段的四个端点正好组成一个平行四边形。于是算法流程非常清晰枚举所有点对 (i, j)i j计算中点 M(i, j)用哈希表统计每个中点被多少条线段共用遍历哈希表对于出现次数为 k 的中点累加 C(k, 2)。这样做的时间复杂度是 O(n²)因为点对数量是 n * (n - 1) / 2而哈希表的插入和查询平均是 O(1)。这个复杂度在实际工程里非常可观。n 5000 时n² 2500 万次枚举C 实测大约几百毫秒n 10000 时n² 1 亿次依然可以在几秒内跑完。比起 O(n^4) 的暴力这是质的飞跃。2.3 中点为什么不直接存浮点整数二倍中点的妙处这里有一个关键细节两个整数相加可能是奇数除以 2 之后会变成小数。比如点 (0, 0) 和 (1, 1) 的中点是 (0.5, 0.5)如果直接存浮点数就需要处理精度问题。浮点数比较是否有误差理论上 double 对于 0.5 这种值是可以精确表示的但如果坐标范围很大比如 10^9 级别的整数相加再除以 2得到的浮点数尾数可能就会有精度损失。在竞赛里这是很致命的两个数学上相等的中点因为舍入误差不同被哈希表判成两个不同的键结果就少算了。解决办法很简单不存中点存“两倍中点”。也就是对于点 A(x1, y1) 和 B(x2, y2)直接存(x1 x2, y1 y2)。因为坐标都是整数两个点的横纵坐标相加结果也是整数不存在精度问题。判断两个点对是否共中点只需要判断它们的坐标和是否完全相等。我第一次接触这个技巧时觉得很惊喜因为它在不引入任何复杂数学的情况下把一类“浮点精度”问题转换成了“整数哈希”问题这是数据结构题里非常经典的思维把不精确的实数域转换到精确的整数域。3. 完整代码实现C 与 Python 双版本3.1 C 实现自定义哈希的 unordered_mapC 的unordered_map默认不支持pairint, int作为键所以需要自己写哈希函数。这一步很考验基本功我见过不少人在面试时卡在这里。一个比较稳妥的哈希写法是把pairint, int转换成一个long long然后直接用标准库的hashlong long#include bits/stdc.h using namespace std; using ll long long; // 将 pairint,int 编码为一个 long long // 注意 x 和 y 可能是负数要加偏移或者做变换 ll encode(pairint, int p) { // 这里假设坐标范围在 [-1e9, 1e9] 之间 // 为了避免负数问题直接把 int 转成 unsigned int 再拼接 return ((ll)(unsigned int)p.first 32) | (unsigned int)p.second; } int main() { int n; cin n; vectorpairint, int points(n); for (int i 0; i n; i) { cin points[i].first points[i].second; } // 去重防止重复点影响结果 sort(points.begin(), points.end()); points.erase(unique(points.begin(), points.end()), points.end()); n points.size(); unordered_mapll, int cnt; cnt.reserve(n * n / 2); for (int i 0; i n; i) { for (int j i 1; j n; j) { int sx points[i].first points[j].first; int sy points[i].second points[j].second; cnt[encode({sx, sy})]; } } long long ans 0; for (auto kv : cnt) { long long k kv.second; ans k * (k - 1) / 2; } cout ans endl; return 0; }这段代码有几个细节值得展开讲。第一encode函数里用(unsigned int)做了无符号转换目的是防止负数在移位时出现符号扩展的问题。如果你直接对负数做左移结果是未定义行为调试起来非常痛苦。第二cnt.reserve(n * n / 2)这一步很关键。哈希表在扩容时会重新哈希所有元素如果不提前预留空间可能在插入过程中频繁扩容带来不必要的性能损耗。实测下来提前 reserve 和不 reserve 在大数据量下能差出 30% 以上的耗时。第三为什么要先去重因为如果输入里有相同的点那么“一条线段”和“另一条相同位置的线段”会被当成两条不同的点对导致重复计数。这个问题我在后面的避坑章节会专门展开。3.2 Python 实现dict 一把梭Python 里用字典做这件事非常爽因为tuple本身就是可哈希的不需要写自定义哈希函数。from collections import defaultdict def count_parallelograms(points): # 去重 points list(set(points)) n len(points) cnt defaultdict(int) for i in range(n): xi, yi points[i] for j in range(i 1, n): xj, yj points[j] mid (xi xj, yi yj) cnt[mid] 1 ans 0 for k in cnt.values(): ans k * (k - 1) // 2 return ans n int(input()) pts [tuple(map(int, input().split())) for _ in range(n)] print(count_parallelograms(pts))这个版本非常简洁核心逻辑不到 20 行。我在带学生的时候经常用这个版本作为“第一次见这道题”的教学版因为它没有任何额外噪声能让学生把注意力集中在算法的思路上。不过要注意Python 的 O(n²) 枚举在 n 超过 3000 时会比较吃力主要是因为 Python 的循环速度远不如 C。如果只是应付面试或者期中期末考试n 在 2000 以内完全没有问题但如果是竞赛题给到 n 10000还是老老实实用 C。3.3 测试用例设计从正方形到一般图形写完代码别急着提交先本地测几个用例。我一般从最简单的图形开始验证。第一个用例是正方形四个点分别是 (0, 0), (1, 0), (1, 1), (0, 1)。这个正方形可以组成 1 个平行四边形也就是它本身。跑代码结果应该是 1。第二个用例是矩形六个点比如 (0, 0), (2, 0), (2, 1), (0, 1), (1, 2), (3, 2)。这个用例比较复杂我建议先画图手算再和代码输出对比。矩形 (0,0)-(2,0)-(2,1)-(0,1) 本身有一个平行四边形再看看 (1,2)-(3,2) 这条线段和哪些线段中点相同……这种人工验证虽然麻烦但能帮助你真正理解“两条对角线共中点”这句话的含义。第三个用例是只有两个点此时没有任何平行四边形答案是 0。第四个用例是三个点共线比如 (0,0), (1,1), (2,2)没有平行四边形答案是 0。设计测试用例时我强烈建议做一次“穷举小规模验证”随机生成 8 个点用 O(n^4) 的暴力做对比再和 O(n²) 的哈希做法比较输出是否一致。这种对拍的方式是竞赛选手的基本功能瞬间暴露算法里的逻辑 bug。4. 复杂度、空间优化与工程取舍4.1 时间空间各花多少心里得有数先算复杂度。枚举点对是 O(n²)每个中点插入哈希表平均 O(1)所以总时间复杂度 O(n²)。空间复杂度就有点意思了最坏情况下每个点对的中点都不同哈希表里会有 O(n²) 个不同的键所以空间复杂度也是 O(n²)。这里有个很容易被忽略的问题n 稍微大一点O(n²) 的空间可能比 O(n²) 的时间更先让你崩溃。假如 n 10000点对数量接近 5000 万如果每个键值对在unordered_map里占用 40 字节左右那光是哈希表就需要近 2 GB 内存这在比赛环境或者面试的白板环境里都不现实。时间复杂度和空间复杂度需要一起考虑这是系统设计的基本素养。我在面试候选人时如果对方只说出 O(n²) 时间而不提空间我会接着问一句“如果 n 很大你的内存够吗”这时候能答出“可以改用排序存储”的人会让我刮目相看。4.2 内存不够时排序替代哈希表哈希表的优势是随机访问 O(1)代价是每个元素有额外的指针开销。如果程序内存受限我们可以换一种思路把所有两倍中点放进一个数组然后排序最后对排序后的数组做一次线性扫描统计相同元素的个数。这样做的时间复杂度是 O(n² log n)排序的复杂度空间复杂度仍然是 O(n²)但由于使用的是紧凑的vector单元素开销比哈希表节点小得多内存占用通常能降低一半以上。vectorll mids; mids.reserve((long long)n * (n - 1) / 2); for (int i 0; i n; i) { for (int j 0; j i; j) { int sx points[i].first points[j].first; int sy points[i].second points[j].second; mids.push_back(encode({sx, sy})); } } sort(mids.begin(), mids.end()); long long ans 0; long long k 1; for (size_t i 1; i mids.size(); i) { if (mids[i] mids[i - 1]) { k; } else { ans k * (k - 1) / 2; k 1; } } ans k * (k - 1) / 2; cout ans endl;这段排序版本的好处不仅在于内存紧凑还在于 cache 友好。vector是连续内存排序时访问局部性很好而unordered_map的节点是散落在堆上的遍历时会频繁发生 cache miss。实测在 n 5000 时排序版本甚至可能比哈希表版本更快。这个取舍很有代表性哈希表和排序是数据结构里两个最基础的工具它们在不同的约束条件下各有优势。做题时一定要先评估数据范围再决定用哪个。4.3 答案数量级估算与 long long 的自觉很多新手在累加答案时用 int结果直接溢出。我们来估算一下答案的最大值。假设 n 个点两两组合出 C(n, 2) 条线段如果这些线段的中点全部相同那么 k C(n, 2)答案 C(k, 2)也就是 C(n,2) * (C(n,2) - 1) / 2。当 n 2000 时C(n,2) 约等于 2 × 10^6答案量级约为 2 × 10^12int 最大只有约 2.1 × 10^9所以用 int 必炸必须用 long long。在 C 里我习惯把涉及计数的变量统统声明为long long虽然看起来保守但能免去无数半夜调 bug 的痛苦。Python 没有这个烦恼因为它的 int 是任意精度的。5. 实战中的坑与排查实录5.1 重复点必须先处理这是我踩过最深的一个坑。有一道类似的题目输入数据里允许出现相同的点。我当时没有去重结果发现答案比标准答案大很多。原因是这样的假设输入有 A 和 A 两个相同点那么线段 AA 的长度为 0中点是 A 本身但它也可以和其他点组成“退化”的线段。更麻烦的是相同点会让“四个顶点”的集合出现重复元素最终导致同一个平行四边形被按多种方式重复计数。解决办法是在读入之后立刻去重。C 里sort加uniquePython 里set直接去重。这个操作是 O(n log n) 的完全不影响整体复杂度。去重之后题目实际上变成“给 n 个互不相同的点”这通常也是很多题面里隐含的默认条件。如果你在面试时发现题面没说主动问一句“输入点会有重复吗”是一个很好的加分项。5.2 四点共线的退化情况怎么办这个坑更深也更隐蔽。比如四个点 (0, 0), (1, 1), (2, 2), (3, 3) 都在同一条直线上。线段 (0,0)-(3,3) 的中点是 (1.5, 1.5)线段 (1,1)-(2,2) 的中点也是 (1.5, 1.5)。按照我们的算法这两个点对会被组合成一个“平行四边形”但实际上四个点都在一条直线上构不成任何平行四边形。这就是经典的四点共线退化情况。那么问题来了如果题面没有保证“无三点共线”我们的算法就是错的。怎么处理常见做法有两种。第一种在统计答案时判断一下四点是否共线这会让代码复杂很多第二种提前检查输入点集中是否存在三点共线的情况如果存在要么题目会特殊说明“共线不算”要么就把这些点排除掉。但严格来说最稳妥的方法是做题前先读清楚数据范围很多竞赛题会直接给出“任意三点不共线”的约束此时这个坑根本不存在。如果是面试场景我建议你主动向面试官确认这个边界条件。因为面试官往往在意的是你能不能在抽象层面把问题建模清楚而不是真的逼你在白板上写一个共线性判断模块。5.3 哈希函数写不好面试直接翻车C 里pairint,int不能直接作为unordered_map的键必须自定义哈希。这个点看起来简单实际写起来门道不少。错误示范是把两个 int 异或起来比如return a.first ^ a.second;。这样会导致大量点对映射到同一个哈希桶哈希表退化成链表复杂度从 O(1) 退化成 O(k)。如果 k 很大整体复杂度就从 O(n²) 退化成了 O(n³)。正确做法是先把pairint, int编码成 64 位整数再交给自己信任的标准哈希函数。我习惯用struct pair_hash { size_t operator()(const pairint, int p) const { return ((size_t)((unsigned int)p.first) 32) | (unsigned int)p.second; } };这样每一对整数都能得到一个几乎不冲突的哈希值实测稳定。记住写哈希函数时宁可“土”一点也不要为了花哨而引入碰撞风险。5.4 计数怎么验证为什么平方和公式不多不少最后验证一下计数公式。以正方形四个顶点为例(0,0), (1,0), (1,1), (0,1)。枚举所有点对得到六条线段其中两条对角线分别是 (0,0)-(1,1) 和 (1,0)-(0,1)它们的中点都是 (1,1)两倍中点表示。所以这个中点的出现次数 k 2C(2, 2) 1答案正好为 1。再看一个稍微复杂的情况如果把正方形每条边的中点也算成新的点那么整个图形变成一个“风车”一样的图形。这个时候可能有多个平行四边形你可以手算一遍再用代码验证。如果手算结果和代码输出对不上多半是你对“不同平行四边形”的定义理解有偏差或者代码里的去重逻辑有问题。在做对拍验证时我通常会把 O(n⁴) 的暴力代码写出来用随机数据跑几百次让两个代码的结果完全一致后才算放心。这个习惯救过我很多次每次都觉得“这么简单的题不可能写错”结果一测就发现边界情况漏了。6. 从平行四边形到更多几何计数问题6.1 如果统计的是矩形呢平行四边形计数是很多几何计数问题的基础版本。如果题目改成统计矩形只需要在“中点”这一个维度上再加一个“对角线长度”的约束。具体来说矩形的充要条件也是对角线互相平分且相等。所以流程变为枚举点对计算中点和线段长度的平方为了避免浮点直接用距离平方然后用一个哈希表去重。对于每个“中点 长度”的组合如果出现 k 次就累加 C(k, 2)。这样统计出来的就是矩形的数量。我当时在面试里遇到过一个变体要求统计正方形数量那就更简单了因为正方形还要求两条对角线长度相等。实际上统计正方形和统计矩形的代码几乎一模一样只是判断条件多一个。这个扩展能帮你把哈希表的应用理解得更通透。6.2 如果统计的是菱形呢统计菱形会比矩形难一些。菱形的特征是“对角线互相垂直且互相平分”所以你的中点和“向量中点”还需要再满足一个垂直条件。一般解法是枚举点对记录中点同时记录线段方向向量 (dx, dy)然后检查“方向向量的点积为 0”的两条线段是否共享中点。这本质上是在做向量之间的垂直关系查找哈希表的键值结构也会更复杂。这种一层套一层的题目在竞赛里特别常见它考察的是你能否把几何判定条件转化为几个“可哈希的原子属性”的组合。一旦你掌握了这种转化方式就能举一反三。6.3 这类题在面试、考研和竞赛中的位置从数据结构知识图谱来看这道题覆盖了哈希表、组合计数、排序去重三大块知识。考研数据结构里哈希表的应用题频率一直很高而这道题恰好是把哈希表的“键值设计”考到了极致你需要自己设计 key 的类型和哈希函数还得理解为什么 key 要设计成两倍中点。竞赛场景下这道题的模板性也很强。区域赛里经常出现“点集计数”类的题目核心往往都是某种几何性质 哈希表/排序。刷透平行四边形计数等于掌握了一大类问题的通法。面试场景就更不用说了。我在模拟面试时经常用这道题考察候选人题目简单到用一句话就能说清但深挖下去会牵扯出内存、哈希冲突、浮点精度、边界情况、复杂度权衡这么多东西非常能反映候选人的代码功底和系统思维。7. 我的一些个人经验与建议说点实在的。我第一次做这道题时犯的错误是直接沿用“暴力枚举四个点”的思路然后剪枝折腾了半天还是 O(n^4)直到看到别人题解里“枚举对角线”这个点才恍然大悟。后来我用这道题给学生讲哈希表几乎每次都会强调数据结构题的关键不在“背模板”而在“找到那个可以把复杂问题简化成键值统计的数学性质”。还有一个小技巧写代码之前先在白纸上把测试用例画出来。几何类题目非常容易在抽象代码里迷失方向画图能让你对“哪两条线段能构成平行四边形”有直观感知写代码时自然不容易出错。如果你在准备期末考试我建议把这道题的完整代码亲手敲一遍然后改一改先改成统计矩形再改成统计正方形。每一步改动都逼着你去思考“哈希键值需要增加哪些维度”这才是真正锻炼数据结构思维的方式。光看不写永远体会不到“把几何性质变成哈希键”的那个瞬间。