LeetCode 3625. 统计梯形的数目 II — Java 实现题目思路核心思想利用容斥原理1. 统计候选四边形含平行四边形枚举所有两点组成的边按「斜率 k → 截距 b」分组。同一斜率下、不同截距的两条直线上的边可构成一组平行对边对应一个候选梯形。2. 统计平行四边形平行四边形的两组对边都平行会在步骤1中被重复计算。利用「平行四边形对角线中点重合」的性质按「中点 → 斜率」分组统计平行四边形数量。3. 最终结果 候选梯形数 − 平行四边形数。Java 代码javaimport java.util.*;class Solution {public int countTrapezoids(int[][] points) {int n points.length;// cnt1: 斜率 k - (截距 b - 该直线上的边数)// 同斜率、不同截距的两条直线上的边可构成一组平行对边MapDouble, MapDouble, Integer cnt1 new HashMap();// cnt2: 中点压缩值 p - (斜率 k - 该中点斜率下的边数)// 同中点、同斜率的两条边构成平行四边形的一组对边MapInteger, MapDouble, Integer cnt2 new HashMap();for (int i 0; i n; i) {int x1 points[i][0], y1 points[i][1];for (int j 0; j i; j) {int x2 points[j][0], y2 points[j][1];int dx x1 - x2;int dy y1 - y2;double k, b;if (dx 0) {// 垂直线斜率标记为无穷大截距为 x 坐标k Double.MAX_VALUE;b x1;} else {k 1.0 * dy / dx;b 1.0 * (y1 * dx - x1 * dy) / dx;}// 处理 -0.0 导致哈希冲突的问题if (k -0.0) k 0.0;if (b -0.0) b 0.0;// 更新 cnt1: 按斜率和截距分组cnt1.computeIfAbsent(k, key - new HashMap()).merge(b, 1, Integer::sum);// 中点压缩将二维中点坐标压缩成一个 int避免浮点精度问题// 坐标范围 [-1000, 1000]中点坐标和范围 [-2000, 2000]// 加上偏移量 2000 后转为非负数再用位移或乘法压缩int midX x1 x2 2000;int midY y1 y2 2000;int p (midX 12) | midY; // 压缩成唯一 int// 更新 cnt2: 按中点和斜率分组cnt2.computeIfAbsent(p, key - new HashMap()).merge(k, 1, Integer::sum);}}int ans 0;// 步骤1统计所有有一组平行对边的四边形数量for (MapDouble, Integer map : cnt1.values()) {int sum 0;for (int c : map.values()) {// 从之前所有直线选1条边 当前直线选1条边ans sum * c;sum c;}}// 步骤2减去平行四边形的数量被重复计算了for (MapDouble, Integer map : cnt2.values()) {int sum 0;for (int c : map.values()) {ans - sum * c;sum c;}}return ans;}}关键点说明要点 说明斜率与截距 垂直线特殊处理斜率用 Double.MAX_VALUE截距用 x 坐标−0.0 处理 k -0.0 或 b -0.0 时统一转为 0.0避免哈希表 key 冲突中点压缩 将中点坐标和x1x2, y1y2平移后压缩为 int避免浮点精度问题组合数计算 用累加和 sum * c 替代 C(n,2)一次遍历完成所有两两组合统计平行四边形扣除 平行四边形在 cnt1 中被统计了 2 次通过 cnt2 减去多算的 1 次复杂度- 时间复杂度O(n^2)枚举所有 n(n-1)/2 条边- 空间复杂度O(n^2)哈希表存储所有边的特征信息