二维整数网格点集任意边矩形计数：求O(n²)级高效算法

给定二维整数网格上的(int x, int y)型点列表，统计所有边不一定平行于x、y轴的矩形数量。

示例 #

• 输入点列表：[(0,0), (0,2), (1,1), (-1, 1)]，返回结果：1
• 输入点列表：[(-1,0), (0, 1), (2,3), (4,1),(2,-1),(1,-2)]，返回结果：3

提供的Java代码框架 #

class Point {
    public int x;
    public int y;
}

class Solution {
    public int countRectangles(List<Point> points) {

    }
}

当前已实现O(n³)复杂度的算法：遍历任意三个点p1、p2、p3，O(1)判断向量p1-p2与p2-p3是否正交，通过数学公式O(1)计算第四个点p4，再O(1)检查p4是否在点集的HashSet中。现询问是否存在O(n²)级的更高效算法？

存在O(n²)复杂度的高效算法，核心思路是利用矩形的对角线性质：矩形的两条对角线互相平分且长度相等；反之，若两个不同点对拥有相同的中点和相同的对角线长度（距离平方），则这四个点必然构成一个矩形。

算法步骤 #

1. 遍历所有i < j的点对（避免重复统计同一对点的反向组合）。
2. 对每个点对(p, q)，计算：
   • 中点坐标的2倍值（用整数存储，规避浮点精度问题）：mid2x = p.x + q.x，mid2y = p.y + q.y
   • 两点间距离的平方（用整数避免浮点运算）：distSq = (p.x - q.x)² + (p.y - q.y)²
3. 用哈希表统计每个(mid2x, mid2y, distSq)组合对应的点对数量。
4. 对每个组合的点对数量k，可组成的矩形数为组合数C(k,2) = k*(k-1)/2，将所有组合的矩形数求和即为最终结果。

Java代码实现 #

import java.util.*;

class Point {
    public int x;
    public int y;
}

class Solution {
    // 自定义哈希表键，存储中点2倍坐标和距离平方
    static class Key {
        long mid2x;
        long mid2y;
        long distSq;

        public Key(long mid2x, long mid2y, long distSq) {
            this.mid2x = mid2x;
            this.mid2y = mid2y;
            this.distSq = distSq;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Key key = (Key) o;
            return mid2x == key.mid2x && mid2y == key.mid2y && distSq == key.distSq;
        }

        @Override
        public int hashCode() {
            return Objects.hash(mid2x, mid2y, distSq);
        }
    }

    public int countRectangles(List<Point> points) {
        Map<Key, Integer> keyCountMap = new HashMap<>();
        int n = points.size();

        // 遍历所有i<j的点对
        for (int i = 0; i < n; i++) {
            Point p = points.get(i);
            for (int j = i + 1; j < n; j++) {
                Point q = points.get(j);
                long mid2x = (long) p.x + q.x;
                long mid2y = (long) p.y + q.y;
                long dx = (long) p.x - q.x;
                long dy = (long) p.y - q.y;
                long distSq = dx * dx + dy * dy;

                Key key = new Key(mid2x, mid2y, distSq);
                keyCountMap.put(key, keyCountMap.getOrDefault(key, 0) + 1);
            }
        }

        // 计算所有组合对应的矩形数量
        int total = 0;
        for (int count : keyCountMap.values()) {
            total += count * (count - 1) / 2;
        }
        return total;
    }
}

复杂度说明 #

• 时间复杂度：O(n²)，仅需遍历所有点对，哈希表操作平均为O(1)。
• 空间复杂度：O(n²)，最坏情况下所有点对的键都不重复，哈希表需存储n(n-1)/2个键值对。

内容的提问来源于stack exchange，提问作者maplemaple