447. 回旋镖的数量.md

447. 回旋镖的数量

class Solution {
     int res = 0;

    public int numberOfBoomerangs(int[][] points) {
        backtrack(points, new LinkedList<>(), 0, new HashSet<>());
        return res;
    }

    private void backtrack(int[][] points, List<int[]> path, int idx, Set<Integer> idSet) {
        if (path.size() == 3) {
            int[] i = path.get(0);
            int[] j = path.get(1);
            int[] k = path.get(2);
            if (eucDistance(i, j) == eucDistance(j, k)) {
                res++;
            }
            return;
        }

        for (int i = 0; i < points.length; i++) {
            if (idSet.contains(i)) {
                continue;
            }
            path.add(points[i]);
            idSet.add(i);
            backtrack(points, path, i + 1, idSet);
            path.remove(path.size() - 1);
            idSet.remove(i);
        }
    }

    private int eucDistance(int[] point1, int[] point2) {
        return (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]);
    }
}

class Solution {
     public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (j == i) {
                    continue;
                }
                for (int k = 0; k < points.length; k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    if (eucDistance(points[i], points[j]) == eucDistance(points[i], points[k])) {
                        res++;
                    }
                }
            }
        }
        return res;
    }

    private int eucDistance(int[] point1, int[] point2) {
        return (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]);
    }
}

class Solution {
     public int numberOfBoomerangs(int[][] points) {

        int res = 0;
        for (int i = 0; i < points.length; i++) {
            Map<Integer, Integer> map = new HashMap<>(points.length / 2);
            for (int j = 0; j < points.length; j++) {
                if (j == i) {
                    continue;
                }
                int dis = eucDistance(points[i], points[j]);
                map.put(dis, map.getOrDefault(dis, 0) + 1);
            }

            for (Integer value : map.values()) {
                if(value == 1) {
                    continue;
                }
                res += value * (value - 1);
            }
        }
        return res;
    }

    private int eucDistance(int[] point1, int[] point2) {
        return (point1[0] - point2[0]) * (point1[0] - point2[0]) + (point1[1] - point2[1]) * (point1[1] - point2[1]);
    }
}