Medium

题目描述

给定二维空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true。

点 pi 的坐标表示为 [xi, yi]。输入没有按任何顺序给出。

有效的正方形具有四条长度相等的边（边长为正数）和四个相等的角（90度角）。

示例 1:

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: true

示例 2:

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出: false

示例 3:

输入: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
输出: true

提示:

  • p1.length == p2.length == p3.length == p4.length == 2
  • -10^4 <= xi, yi <= 10^4

解题思路

解题思路

判断四个点是否构成正方形，关键在于验证正方形的几何特性：

  1. 四条边相等且长度大于0
  2. 两条对角线相等
  3. 对角线长度是边长的√2倍

方法一：距离分析法（推荐）

计算任意两点间的距离，正方形应该有4条相等的边和2条相等的对角线。具体步骤：

  1. 计算所有点对之间的距离的平方（避免浮点运算）
  2. 对距离进行排序
  3. 检查是否恰好有4个相等的较小距离（边）和2个相等的较大距离（对角线）
  4. 验证对角线长度是边长的2倍（因为我们用的是距离的平方）

方法二：向量法

选择一个点作为基准，计算到其他三个点的向量，验证是否存在两个垂直且等长的向量。

方法三：中心点法

计算四个点的中心，验证所有点到中心的距离相等，且相邻点之间的夹角为90度。

距离分析法最直观且容易实现，是最推荐的解法。

代码实现

class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        vector<vector<int>> points = {p1, p2, p3, p4};
        vector<long long> distances;
        
        // 计算所有点对之间的距离的平方
        for (int i = 0; i < 4; i++) {
            for (int j = i + 1; j < 4; j++) {
                long long dx = points[i][0] - points[j][0];
                long long dy = points[i][1] - points[j][1];
                distances.push_back(dx * dx + dy * dy);
            }
        }
        
        sort(distances.begin(), distances.end());
        
        // 正方形应该有4条相等的边和2条相等的对角线
        // 边长不能为0，对角线长度应该是边长的√2倍（平方后是2倍）
        return distances[0] > 0 && 
               distances[0] == distances[1] && 
               distances[1] == distances[2] && 
               distances[2] == distances[3] && 
               distances[4] == distances[5] && 
               distances[0] * 2 == distances[4];
    }
};

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        points = [p1, p2, p3, p4]
        distances = []
        
        # 计算所有点对之间的距离的平方
        for i in range(4):
            for j in range(i + 1, 4):
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]
                distances.append(dx * dx + dy * dy)
        
        distances.sort()
        
        # 正方形应该有4条相等的边和2条相等的对角线
        # 边长不能为0，对角线长度应该是边长的√2倍（平方后是2倍）
        return (distances[0] > 0 and 
                distances[0] == distances[1] == distances[2] == distances[3] and
                distances[4] == distances[5] and 
                distances[0] * 2 == distances[4])

public class Solution {
    public bool ValidSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        int[][] points = {p1, p2, p3, p4};
        List<long> distances = new List<long>();
        
        // 计算所有点对之间的距离的平方
        for (int i = 0; i < 4; i++) {
            for (int j = i + 1; j < 4; j++) {
                long dx = points[i][0] - points[j][0];
                long dy = points[i][1] - points[j][1];
                distances.Add(dx * dx + dy * dy);
            }
        }
        
        distances.Sort();
        
        // 正方形应该有4条相等的边和2条相等的对角线
        // 边长不能为0，对角线长度应该是边长的√2倍（平方后是2倍）
        return distances[0] > 0 && 
               distances[0] == distances[1] && 
               distances[1] == distances[2] && 
               distances[2] == distances[3] && 
               distances[4] == distances[5] && 
               distances[0] * 2 == distances[4];
    }
}

/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 */
var validSquare = function(p1, p2, p3, p4) {
    const points = [p1, p2, p3, p4];
    const distances = [];
    
    // 计算所有点对之间的距离的平方
    for (let i = 0; i < 4; i++) {
        for (let j = i + 1; j < 4; j++) {
            const dx = points[i][0] - points[j][0];
            const dy = points[i][1] - points[j][1];
            distances.push(dx * dx + dy * dy);
        }
    }
    
    distances.sort((a, b) => a - b);
    
    // 正方形应该有4条相等的边和2条相等的对角线
    // 边长不能为0，对角线长度应该是边长的√2倍（平方后是2倍）
    return distances[0] > 0 && 
           distances[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(1)固定计算6个距离并排序，常数时间
空间复杂度O(1)使用固定大小的数组存储距离