平面上回旋镖数量求解算法

题目

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输入:

[[0,0],[1,0],[2,0]]

输出:

2

解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

php 实现

class Solution {

    /**
     * @param Integer[][] $points
     * @return Integer
     */
    function numberOfBoomerangs($points) {
        $total = 0;
        if(!$points) {
            return $total;
        }

        $hash = [];
        $total_arr = [];
        foreach($points as $_k1 => $_v1) {
            foreach($points as $_k2 => $_v2) {
                if($_k1 == $_k2) {
                    continue;
                }
                $length = $this->getLength($_v1, $_v2);
                if(!isset($hash[$_k1][$length])) {
                    $hash[$_k1][$length] = 1;
                } else {
                    if(!isset($total_arr[$_k1])) {
                        $total_arr[$_k1] = $hash[$_k1][$length] * 2;
                    } else {
                        $total_arr[$_k1] += $hash[$_k1][$length] * 2;
                    }
                    $hash[$_k1][$length] ++;
                }
            }
        }

        return array_sum($total_arr);
    }

    function getLength($i, $j)
    {
        $x2 = ($i[0] - $j[0]) * ($i[0] - $j[0]);
        $y2 = ($i[1] - $j[1]) * ($i[1] - $j[1]);
        return $x2 + $y2;
    }
}

Golang实现

package main

import (
    "fmt"
)

func main() {
    points := [][]int{
        {0,0},
        {1,0},
        {2,0},
    }
    num := numberOfBoomerangs(points)
    fmt.Println(num)
}

func numberOfBoomerangs(points [][]int) int {
    ans := 0
    hash := map[int]int{}
    for i:= 0;i<len(points);i++{
        for j:=0;j<len(points);j++ {
            if(i == j) {
                continue
            }
            length := getLength(points[i], points[j]);
            if hash[length] > 0 {
                ans += hash[length] * 2
            }
            hash[length] ++
        }
        hash = map[int]int{}
    }
    return ans
}

func getLength(p1 []int, p2 []int) int {
    return ((p1[0] - p2[0]) * (p1[0] - p2[0])) + ((p1[1] - p2[1]) * (p1[1] - p2[1]))
}

关键要理解：

以k1为起点的回旋镖，只要到k1长度相同的点数量($hash[$_k1][$length])增加1个，那k1可以组成的回旋镖数量就是在现有数量$total_arr[$_k1]基础上， 加上$hash[$_k1][$length] * 2