Number of Boomerangs

https://leetcode.com/problems/number-of-boomerangs/description/

Givennpoints in the plane that are all pairwise distinct, a "boomerang" is a tuple of points(i, j, k)such that the distance betweeniandjequals the distance betweeniandk(the order of the tuple matters).

Find the number of boomerangs. You may assume thatnwill be at most500and coordinates of points are all in the range[-10000, 10000](inclusive).

Thoughts

问题是要对于所有点，把和该点距离相同的按序抽出两个。因此我们可以对每个点统计下和它距离相同的点所形成的set， 对每个set抽俩。

Code

class Solution {
    private int getDistance(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];

        return dx*dx + dy*dy;
    }

    public int numberOfBoomerangs(int[][] points) {
        Map[] maps = new Map[points.length];
        for (int i = 0; i < points.length; i++) {
            maps[i] = new HashMap<Integer, Integer>();
            Map<Integer, Integer> map = maps[i];
            for (int j = 0; j < points.length; j++) {
                if (j == i) {
                    continue;
                }
                int distance = getDistance(points[i], points[j]);
                if (!map.containsKey(distance)) {
                    map.put(distance, 1);
                } else {
                    map.put(distance, (int)map.get(distance) + 1);
                }
            }
        }

        int res = 0;
        for (Map<Integer, Integer> map : maps) {
            for (Integer dis : map.keySet()) {
                if (map.get(dis) > 1) {
                    res += map.get(dis) * (map.get(dis) - 1);
                }
            }
        }

        return res;
    }
}

Analysis

时间复杂度O(n^2), 空间O(n^2).

Ver.2

可以重复利用一个map.

class Solution {
    private int getDistance(int[] a, int[] b) {
        int dx = a[0] - b[0];
        int dy = a[1] - b[1];

        return dx*dx + dy*dy;
    }

    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (j == i) {
                    continue;
                }
                int distance = getDistance(points[i], points[j]);
                if (!map.containsKey(distance)) {
                    map.put(distance, 1);
                } else {
                    map.put(distance, (int)map.get(distance) + 1);
                }
            }

            for (Integer dis : map.keySet()) {
                if (map.get(dis) > 1) {
                    res += map.get(dis) * (map.get(dis) - 1);
                }
            }
            map.clear();
        }

        return res;
    }
}