著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.
这是一道数学题.注意回旋镖的定义,其实就是求二维坐标内是否存在三个不同的点,两两之间的距离相等.如果是暴力解,那么起码是 O(n^3) 级别的复杂度,因为需要枚举三个不同的点.这里为了降低复杂度,我们可以考虑,对于同一个点 i 来说,我们能找到多少 (j k) 的组合,使得 j 和 k 分别到 i 的距离是相等的.计算坐标系内两点之间的距离的步骤其实不需要开根号,参见代码中 helper 函数.
所以这里我们需要一个两层 for 循环,第一层是遍历 i ,第二层是遍历其他所有的点,看看有多少个不同的距离 distance.最后统计的时候是 count * (count - 1).