(14)Go查找表求回旋镖数量

1）暴力解法：时间复杂度O(n^3)

2)查找表
通过题目可以看出每一个点 i 都是一个枢纽，对于每个点 i，遍历其余点到 i 的距离，存储到查找表
时间复杂度O(n^2)
空间复杂度为O((n-1)+(n-2)+...+1) = O(n)

实现
// 时间复杂度O(n^2)
// 空间复杂度最大为O((n-1)+(n-2)+...+1) = O(n)
func numberOfBoomerangs(points [][]int) int {
    count := 0

    for i1, v1 := range points {
        // m[key]val: key为值,val为出现的次数
        m := make(map[int]int)

        for i2, v2 := range points {
            if i1 != i2 {
                m[distance(v1, v2)]++
            }
        }

        // val>1,则有 val * (val - 1) 个三元组
        for _, v := range m {
            if v > 1 {
                count += v * (v - 1)
            }
        }
    }

    return count
}

// 计算两点距离的平方
func distance(a, b []int) int {
    return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])
}

提交leetcode，通过