2013. 检测正方形

approach 1，哈希表

class DetectSquares {
    Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
    public DetectSquares() {
    }
    
    public void add(int[] point) {
        int x = point[0], y = point[1];
        Map<Integer, Integer> ymap = map.getOrDefault(x, new HashMap<Integer, Integer>());
        ymap.put(y, ymap.getOrDefault(y, 0) + 1);
        map.put(x, ymap);
    }
    
    public int count(int[] point) {
        int x = point[0], y = point[1];
        Map<Integer, Integer> ymap = map.get(x);
        if (ymap == null) return 0;
        int ans = 0;
        for (int ny : ymap.keySet()) {
            if (ny == y) continue;
            int d = Math.abs(ny - y);
            int cnt = ymap.get(ny);
            Map<Integer, Integer> am = map.getOrDefault(x + d, new HashMap<>());
            Map<Integer, Integer> bm = map.getOrDefault(x - d, new HashMap<>());
            ans += cnt * am.getOrDefault(ny, 0) * am.getOrDefault(y, 0);
            ans += cnt * bm.getOrDefault(ny, 0) * bm.getOrDefault(y, 0);
        }
        return ans;
    }
}

一样的做法，写法略微改了点

class DetectSquares {
    Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
    public DetectSquares() {
    }
    
    public void add(int[] point) {
        int x = point[0], y = point[1];
        Map<Integer, Integer> ymap = map.getOrDefault(x, new HashMap<>());
        ymap.put(y, ymap.getOrDefault(y, 0) + 1);
        map.put(x, ymap);
    }
    
    public int count(int[] point) {
        int x = point[0], y = point[1];
        Map<Integer, Integer> ymap = map.get(x);
        if (ymap == null) return 0;
        int ans = 0;
        for (int ny : ymap.keySet()) {
            if (ny == y) continue;
            int d = y - ny;
            int c1 = ymap.get(ny);
            int[] nums = new int[]{x + d, x - d};
            for (int nx : nums) {
                Map<Integer, Integer> ytmp = map.getOrDefault(nx, new HashMap<>());
                int c2 = ytmp.getOrDefault(ny, 0), c3 = ytmp.getOrDefault(y, 0);
                ans += c1 * c2 * c3;
            }
        }
        return ans;
    }
}