LeetCode 593. 有效的正方形

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

题目描述

✅ 593. 有效的正方形

image-20260928235824607

题意分析

判断平面上的四个点能否构成一个边长大于零、四个角都是直角的正方形。输入没有顺时针或逆时针顺序，正方形也可以倾斜，不能直接把输入中相邻的点认作一条边。

四点一共形成六条两点间线段。正方形中，它们恰好是四条边和两条对角线，因此可以从全部距离的关系判断形状，不必先给四个顶点排序。

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

核心思路

[!blue]

用 $d(a,b)=(a_x-b_x)^2+(a_y-b_y)^2$ 表示距离平方。只比较平方即可判断长度是否相等，省去了开方与浮点误差。设正方形的边长平方为 $s$，勾股定理给出对角线平方为 $2s$，所以六个距离排序后必须是 $[s,s,s,s,2s,2s]$，且 $s>0$。

这组条件也足以确定正方形。两条较长线段不可能共享端点：若它们是 $AB$ 和 $AC$，第四点为 $D$，则 $DA$、$DB$、$DC$ 和 $BC$ 的长度均为 $\sqrt{s}$。由勾股定理的逆定理，$DB$ 和 $DC$ 都要垂直于 $DA$，于是 $B$、$C$ 只能重合，或位于 $D$ 两侧而相距 $2\sqrt{s}$；这都与 $BC=\sqrt{s}$ 矛盾。

因此，两条较长线段连接的是不相交的两对顶点，恰好可以作为对角线。剩余四条线段等长，且每个角两边的平方和 $s+s$ 都等于对面线段的平方 $2s$，所以四个角都是直角。再加上 $s>0$ 排除了重合点，得到的就是有效正方形。

排序后不必逐对比较前四项：dist[0] == dist[3] 已能保证夹在中间的两项也相等。再检查 dist[4] == dist[5] 和 dist[4] == 2 * dist[0]，便覆盖了全部距离关系。

解题步骤

  • 枚举四点间全部六对组合，计算平方距离；代码使用 long 或 int64 保存计算结果。
  • 将距离排序。
  • 确认最小距离大于零，并用第一项与第四项相等验证四条短线段等长。
  • 确认最后两项相同，且均为最小项的两倍；所有条件成立才返回 true。

代码实现

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)$，始终只有六个距离。
  • 空间复杂度：$O(1)$，固定六项数组。

关键点总结

[!green]

  • 六个距离不受顶点输入顺序或图形旋转影响，排序只是将短边与长对角线分开。
  • 四条短距离相等、两条长距离相等且为前者的两倍，共同刻画正方形的边和直角。
  • 最小距离为零意味着至少两点重合，必须先排除退化情况。

易错点总结

[!yellow]

  • 直接把输入相邻点当边，会误判打乱顺序的正方形。
  • 不检查正长度，四点重合会被接受。
  • 只比较四条候选边，不能排除非正方形菱形。

相似题目

题目 难度 关联与区别
963. 最小面积矩形 II 中等 同样判断四点能否构成规则四边形，原题寻找矩形，本题还必须保证四条边等长且非零。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/58606642
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！