What is the most efficient approach to solve Number of Boomerangs?

Use each point as a pivot and compute distances to all other points with a hash map to count frequencies, then sum count*(count-1) for each distance.

Why use squared distances instead of actual distances?

Squared distances avoid floating point errors and expensive square root calculations while preserving equality checks required for boomerangs.

Can this approach handle large point sets efficiently?

Yes, with n up to 500, using O(n^2) time and O(n) space per pivot is feasible and avoids redundant distance recalculations.

How does the hash map improve performance in this pattern?

It allows counting all points at the same distance from the pivot in O(1) per insertion, efficiently computing permutations for boomerangs.

What common mistakes should I avoid in Number of Boomerangs?

Avoid using square roots, miscounting tuple orders, and forgetting to reset the distance map between pivot points.

#447

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

回旋镖的数量

给定平面上 n 对互不相同的点 points ，其中 points[i] = [x i , y i ] 。回旋镖是由点 (i, j, k) 表示的元组，其中 i 和 j 之间的欧式距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。返回平面上所有回旋镖的数量。示例 1： …

数组哈希表数学

题目描述

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [x_i, y_i] 。回旋镖 是由点 (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⁴ <= x_i, y_i <= 10⁴
所有点都 互不相同

lightbulb

解题思路

方法一：枚举 + 计数

我们可以枚举 points 中的每个点作为回旋镖的点 $i$ ，然后用一个哈希表 $cnt$ 记录其他点到 $i$ 的距离出现的次数。

如果有 $x$ 个点到 $i$ 的距离相等，那么我们可以任选其中 $2$ 个点作为回旋镖的 $j$ 和 $k$ ，方案数为 $A_x^2 = x \times (x - 1)$ 。因此，我们对哈希表中的每个值 $x$ ，都计算并累加 $A_x^2$ ，就可以得到满足题目要求的回旋镖数量之和。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 points 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p1 in points:
            cnt = Counter()
            for p2 in points:
                d = dist(p1, p2)
                ans += cnt[d]
                cnt[d] += 1
        return ans << 1

speed

复杂度分析

指标	值
时间	complexity is O(n^2) because each point is used as a pivot and distances are computed to all other points. Space complexity is O(n) for the hash map storing distances per pivot point.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They may hint at optimizing distance calculations using squared distances instead of square roots.
question_mark
Expect clarifying questions about handling duplicate distances efficiently with hash maps.
question_mark
They may ask about edge cases such as a single point or collinear points where boomerangs are limited.

warning

常见陷阱

外企场景

error
Calculating Euclidean distance with square roots can introduce floating point errors; always use squared distance.
error
Failing to multiply frequency by (frequency - 1) for ordering of tuples will give incorrect counts.
error
Resetting the hash map incorrectly between pivot points can mix distances and produce wrong totals.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Counting boomerangs in 3D points instead of 2D using the same array scanning plus hash lookup pattern.
arrow_right_alt
Finding boomerangs where distances satisfy a specific ratio rather than equality.
arrow_right_alt
Modifying the problem to return all boomerang tuples explicitly instead of just the count.

help

常见问题

外企场景

继续练习

#391 完美矩形 #381 O(1) 时间插入、删除和获取随机元素 - 允许重复 #380 O(1) 时间插入、删除和获取随机元素