447. Number of Boomerangs

447. Number of Boomerangs

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between iand j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

My Solutions:

如果有点a，b和c，如果ab和ac之间的距离相等，那么就有两种排列方法abc和acb；如果有三个点b，c，d都分别和a之间的距离相等，那么有六种排列方法，abc, acb, acd, adc, abd, adb。如果有n个点和a距离相等，那么排列方式为n(n-1)

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if(points == null || points.length == 0 || points[0].length == 0) return 0;
        
        int res = 0;
        
        for (int[] p1 : points) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int[] p2 : points) {
                if (p1 == p2) continue;
                int x = p1[0] - p2[0];
                int y = p1[1] - p2[1];
                int dist = x * x + y * y;
                map.put(dist, map.getOrDefault(dist, 0) + 1);
            }
            for (int n : map.values()) res += n * (n - 1);
        }
        return res;
    }
}

如果想要运行速度更快，可以如下

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        
        Map<Integer, Integer> map = new HashMap<>(); //不要每次新建map，用map.clear()
        int count = 0;
        
        for (int[] p1 : points) {
            for (int[] p2 : points) {
                if (p1 == p2) {
                    continue;
                }
                
                int x = p1[0] - p2[0];
                int y = p1[1] - p2[1];
                int dis = x*x + y*y;
                
                int n = map.getOrDefault(dis, 0);
                
                map.put(dis, n + 1); //map只记录点的个数
                count += n; //e.g. 当只有一个点时，count += 0；有两个点，count+=1, count = 1；有三个点，count+=2，count = 3
            }
            map.clear(); 
        }
        return count * 2; //e.g.有两个点，count = 1, 有2种方式；三个点，count =3，有6种可能的方式
    }
}