2857. 统计距离为 k 的点对 (opens new window)

1.逆向枚举

枚举任意两个点并计算距离，时间复杂度为O(n*n)。有什么方法可以简化时间复杂度？

采用已知点和距离枚举“点”的方法，其中和为k共有k+1种组合(0,k),(1,k-1)... 时间复杂度O(n*k)

注意多个点处于同一个坐标的情况，采用哈希表保存节点和出现频次。

class Solution {
    public int countPairs(List<List<Integer>> coordinates, int k) {
        int res=0;
        Map<Long,Integer> map=new HashMap<>();
        for(int i=0;i<coordinates.size();i++){
            int x=coordinates.get(i).get(0),y=coordinates.get(i).get(1);
            long key=1L*2000000*x+y;
            map.put(key,map.getOrDefault(key,0)+1);
        }
        for(int i=0;i<coordinates.size();i++){
            int x=coordinates.get(i).get(0),y=coordinates.get(i).get(1);
            long key1=1L*x*2000000+y;
            for(int j=0;j<=k;j++){
                int x2=x^j,y2=y^(k-j);
                long key2=1L*x2*2000000+y2;
                if(map.containsKey(key2)){
                    res+=key2==key1?map.get(key2)-1:map.get(key2);
                } 
            }
            if(map.get(key1)==1) map.remove(key1);
            else map.put(key1,map.get(key1)-1);
        }
        return res;
    }
}