Medium

题目描述

给定平面上 n 个不同的点，其中 points[i] = [xi, yi]。回旋镖是由点 (i, j, k) 组成的元组，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（元组的顺序很重要）。

返回回旋镖的数量。

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例 3：

输入：points = [[1,1]]
输出：0

提示：

  • n == points.length
  • 1 <= n <= 500
  • points[i].length == 2
  • -10^4 <= xi, yi <= 10^4
  • 所有点都是唯一的

解题思路

解题思路

这道题要求找到所有满足条件的回旋镖，即对于三个点 (i, j, k)，点 i 到点 j 的距离等于点 i 到点 k 的距离。

核心思想：枚举中心点

对于每个点作为回旋镖的中心点 i，我们需要找到有多少对点 (j, k) 满足 distance(i,j) = distance(i,k)。

算法步骤：

  1. 遍历每个点作为中心点 i
  2. 对于当前中心点，计算它到其他所有点的距离
  3. 使用哈希表统计相同距离的点的个数
  4. 如果有 n 个点到中心点的距离相同，那么可以形成 n×(n-1) 个回旋镖（因为顺序重要）

距离计算优化： 为了避免浮点数精度问题，我们可以使用距离的平方来比较，即 (x1-x2)² + (y1-y2)²。

时间复杂度分析：

  • 外层循环遍历 n 个点作为中心点：O(n)
  • 内层循环计算到其他点的距离：O(n)
  • 总时间复杂度：O(n²)

代码实现

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int result = 0;
        
        for (int i = 0; i < points.size(); i++) {
            unordered_map<int, int> distCount;
            
            for (int j = 0; j < points.size(); j++) {
                if (i == j) continue;
                
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                int distSquare = dx * dx + dy * dy;
                
                distCount[distSquare]++;
            }
            
            for (auto& pair : distCount) {
                int count = pair.second;
                if (count >= 2) {
                    result += count * (count - 1);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        result = 0
        
        for i in range(len(points)):
            dist_count = {}
            
            for j in range(len(points)):
                if i == j:
                    continue
                
                dx = points[i][0] - points[j][0]
                dy = points[i][1] - points[j][1]
                dist_square = dx * dx + dy * dy
                
                dist_count[dist_square] = dist_count.get(dist_square, 0) + 1
            
            for count in dist_count.values():
                if count >= 2:
                    result += count * (count - 1)
        
        return result

public class Solution {
    public int NumberOfBoomerangs(int[][] points) {
        int result = 0;
        
        for (int i = 0; i < points.Length; i++) {
            Dictionary<int, int> distCount = new Dictionary<int, int>();
            
            for (int j = 0; j < points.Length; j++) {
                if (i == j) continue;
                
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                int distSquare = dx * dx + dy * dy;
                
                if (distCount.ContainsKey(distSquare)) {
                    distCount[distSquare]++;
                } else {
                    distCount[distSquare] = 1;
                }
            }
            
            foreach (var pair in distCount) {
                int count = pair.Value;
                if (count >= 2) {
                    result += count * (count - 1);
                }
            }
        }
        
        return result;
    }
}

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfBoomerangs = function(points) {
    let count = 0;
    
    for (let i = 0; i < points.length; i++) {
        let distanceMap = new Map();
        
        for (let j = 0; j < points.length; j++) {
            if (i !== j) {
                let dx = points[i][0] - points[j][0];
                let dy = points[i][1] - points[j][1];
                let distance = dx * dx + dy * dy;
                
                distanceMap.set(distance, (distanceMap.get(distance) || 0) + 1);
            }
        }
        
        for (let freq of distanceMap.values()) {
            count += freq * (freq - 1);
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历每个点作为中心点，并计算到其他所有点的距离
空间复杂度O(n)哈希表最多存储 n-1 个不同的距离值

相关题目