题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组，找到其中所有三元组的数量。要求三元组之中，（假定顺序为 i，j，k），那么 i 和 k 的欧氏距离 i 和 j 的欧氏距离相等。

思路分享

  • 基本的枚举思路可以参考【Leetcode Daily】2909元素和最小的山形三元组。

  • 和之前的题思路不同，此题需要在每次循环枚举 i 时都维护一个哈希表，该哈希表为各元素与 i 的欧氏距离。一旦遍历到曾经与自己距离相同的元素，结果则多加了两个。（之所以是两个，是因为三元组中的 j 和 k 可以互换位置。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for xi, yi in points:
            rec = defaultdict(int)
            for xj, yj in points:
                disij = (xi - xj)**2 + (yi - yj)**2
                ans += rec[disij] * 2
                rec[disij] += 1

        return ans