以下是 LeetCode 3625. 统计梯形的数目 II 的 Python3 实现。核心思路1. 统计所有有一组平行对边的四边形枚举所有点对构成的线段按斜率 → 截距分组。同一斜率下从不同截距的直线各选一条边即可构成一组平行对边。2. 减去平行四边形的重复计数平行四边形有两组平行对边会在步骤 1 中被统计 2 次。利用平行四边形对边中点相同的性质按中点 → 斜率分组统计平行四边形数量从答案中扣除。pythonfrom typing import Listfrom collections import defaultdictclass Solution:def countTrapezoids(self, points: List[List[int]]) - int:n len(points)# cnt1: 斜率 k - 截距 b - 该直线上的边数cnt1: dict[float, dict[float, int]] defaultdict(lambda: defaultdict(int))# cnt2: 中点编码 p - 斜率 k - 边数用于识别平行四边形cnt2: dict[int, dict[float, int]] defaultdict(lambda: defaultdict(int))for i in range(n):x1, y1 points[i]for j in range(i):x2, y2 points[j]dx x2 - x1dy y2 - y1# 计算斜率 k 和截距 bif dx 0:# 垂直线斜率用 inf 标记截距为 x 坐标k float(inf)b float(x1)else:k dy / dx# 截距 b (y1 * dx - x1 * dy) / dx# 用 int64 避免中间溢出b (y1 * dx - x1 * dy) / dx# 统一 -0.0 为 0.0避免哈希冲突if k 0.0:k 0.0if b 0.0:b 0.0cnt1[k][b] 1# 中点编码将二维坐标压缩成一个 int避免浮点精度问题# 坐标范围 [-1000, 1000]和的范围 [-2000, 2000]# 平移 2000 后编码p (x1 x2 2000) * 4000 (y1 y2 2000)cnt2[p][k] 1ans 0# 步骤1统计所有有一组平行对边的四边形含平行四边形# 同一斜率下从不同截距的直线各选一条边for m in cnt1.values():s 0for c in m.values():ans s * c # 从之前的直线选1条 当前直线选1条s c# 步骤2减去平行四边形的重复计数# 平行四边形在 cnt1 中被算了2次这里减去多算的1次# 同一中点 同一斜率的两条边构成平行四边形的一组对边for m in cnt2.values():s 0for c in m.values():ans - s * cs creturn ans关键点说明要点 说明斜率分组 同斜率 不同截距 平行且不共线可构成梯形的一组对边中点编码 平行四边形的两组对边中点相同(x1x2, y1y2) 压缩成单个 int 避免浮点误差累加计数 s * c 等价于从之前所有直线选一条、当前直线选一条的组合数比 C(n,2) 更高效-0.0 处理 Python 中 dy/dx 当 dy0 时可能产生 -0.0统一为 0.0 防止哈希表冲突复杂度分析- 时间复杂度O(n^2)枚举所有 O(n^2) 条边哈希操作均摊 O(1)。- 空间复杂度O(n^2)最坏情况下每条边对应唯一的斜率/截距/中点组合。