LeetCode 593. 有效的正方形

约 5 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节跳动 腾讯 华为
标签
数学 几何
目录

题目描述

✅ 593. 有效的正方形

题意分析

给出平面上四个点，判断它们能否恰好构成一个正方形。四个点是无序给出的，题目没有承诺 p1 p2 p3 p4 按逆时针或顺时针排列，所以任何依赖「相邻」关系的判断都必须自己先把顺序理出来。

正方形的定义要求四条边等长、四个角是直角，等价地也可以说四条边等长且两条对角线等长。要点在于「四边等长」单独不够——菱形也满足；「对角线等长」单独也不够——矩形也满足。

约束信号：坐标范围是 $[-10^4, 10^4]$，都是整数。整数坐标意味着两点距离的平方一定是整数，最大值约 $8 \times 10^8$，在 32 位整数范围内，可以完全避开开方带来的浮点误差。

边界情况：四个点允许重合。四点全部落在同一位置时，所有「边长」都是 0，退化图形不是正方形，必须显式排除；两点或三点重合的情况同样要返回假。

解法：六个距离平方排序判断

核心思路

输入没有顺序，直接把 p1-p2 当作一条边会漏判。与其枚举 $4!$ 种点序，不如使用与点序无关的量：4 个点共有 $C_4^2=6$ 个两两距离。

若正方形边长平方为 $s$，6 个距离平方排序后一定是

\[[s,s,s,s,2s,2s],\quad s>0\]

前 4 个是边，后 2 个是对角线；勾股定理给出对角线平方为 $2s$。反过来，这个非零距离模式也把四点连接成两条全等的等腰直角三角形，因此足以判定正方形。

所以判断条件可压缩为：d[0] > 0、d[0] == d[3]、d[4] == d[5]、d[4] == 2*d[0]。其中 d[0] > 0 是退化保护，不能省略。

全程比较距离平方，不开方。题目坐标下 32 位整数也不会溢出；实现仍用 long/int64，并在做减法前转换类型，避免代码复用到更大坐标时先在 int 中溢出。

解题步骤

  1. 枚举四点的全部 6 个点对，计算距离平方 $dx^2+dy^2$。
  2. 将 6 个距离平方升序排序，让边与对角线自然分组。
  3. 检查最短距离非零，排除重合点形成的退化图形。
  4. 检查前 4 个距离相等、后 2 个距离相等，并验证后者是前者的 2 倍。

以 p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] 走一遍：注意输入顺序是「对角、对角」交错的，不是沿边给出的。

六个距离平方为 $[2,1,1,1,1,2]$，排序后是 $[1,1,1,1,2,2]$。最短距离非零，前四项相等，后两项相等且 $2=2\times1$，返回 true。

菱形反例 [[0,0],[1,2],[2,0],[1,-2]] 的距离平方排序后为 $[4,5,5,5,5,16]$。它虽然四边等长，但两条对角线不等，不符合目标模式。

代码实现

import java.util.Arrays;

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        long[] dist = {
            distance(p1, p2), distance(p1, p3), distance(p1, p4),
            distance(p2, p3), distance(p2, p4), distance(p3, p4)
        };
        Arrays.sort(dist);

        return dist[0] > 0
            && dist[0] == dist[3]
            && dist[4] == dist[5]
            && dist[4] == 2 * dist[0];
    }

    private long distance(int[] a, int[] b) {
        long dx = (long) a[0] - b[0];
        long dy = (long) a[1] - b[1];
        return dx * dx + dy * dy;
    }
}

import "sort"

func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
    dist := []int64{
        squareDistance(p1, p2), squareDistance(p1, p3), squareDistance(p1, p4),
        squareDistance(p2, p3), squareDistance(p2, p4), squareDistance(p3, p4),
    }
    sort.Slice(dist, func(i, j int) bool { return dist[i] < dist[j] })

    return dist[0] > 0 &&
        dist[0] == dist[3] &&
        dist[4] == dist[5] &&
        dist[4] == dist[0]*2
}

func squareDistance(a []int, b []int) int64 {
    dx := int64(a[0]) - int64(b[0])
    dy := int64(a[1]) - int64(b[1])
    return dx*dx + dy*dy
}

复杂度分析

  • 时间复杂度：$O(1)$。固定计算 6 个距离，并排序长度为 6 的数组。
  • 空间复杂度：$O(1)$。距离数组长度固定。

关键点总结

  • 六距离的有序模式是输入顺序无关的不变量，比枚举点序更短、更稳。
  • 距离平方既保留大小与相等关系，又避免浮点误差。
  • d[0] > 0 排除退化；4 条等边排除一般矩形；2 条等长且满足 2 倍关系的对角线排除一般菱形。
  • 先扩为宽类型再做减法，才真正解决溢出问题；乘完再转换已经来不及。

易错点总结

  • 假设输入沿边排列：乱序正方形 [[0,0],[1,1],[1,0],[0,1]] 会被误判；必须计算全部 6 对距离。
  • 忘记非零条件：四点全为 [0,0] 时，所有相等与 2 倍关系都成立，却不是正方形。
  • 只检查四条边：一般菱形也有四条等边；还要检查两条对角线及 2 倍关系。
  • 开方后比较浮点数：没有必要承担精度风险，直接比较整数距离平方。
  • 错误处理溢出：long dx = a[0] - b[0] 仍会先执行 int 减法；应写成 long dx = (long) a[0] - b[0]。

相似题目

题目 难度 考察点
836. 矩形重叠 简单 区间投影相交，无需距离计算
812. 最大三角形面积 简单 叉积求面积并枚举取最大值
223. 矩形面积 中等 容斥求并集面积，重点在重叠区域计算
149. 直线上最多的点数 困难 用约分后的斜率做哈希键，规避浮点误差