Number of Boomerangs - Hash Table - Easy - LeetCode

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 i and 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]]

public class Solution {
 public int NumberOfBoomerangs(int[][] points) {
 int res = 0;

 var map = new Dictionary<int,int>();
 for(int i=0; i<points.Length; i++) {
 for(int j=0; j<points.Length; j++) {
 if(i == j)
 continue;

 int d = getDistance(points[i], points[j]); 
 if(map.ContainsKey(d)){
 map[d]++;
 }
 else{
 map.Add(d,1);
 } 
 }

 foreach(var item in map) {
 res += item.Value * (item.Value-1);
 } 
 map.Clear();
 }

 return res;
 }
 
 private int getDistance(int[] a, int[] b) {
 int dx = a[0] - b[0];
 int dy = a[1] - b[1];

 return dx*dx + dy*dy;
 }
}

Time Complexity: O(n^2)

Space Complexity: O(n)

the val * (val-1); means permutations A(n,2)=n*(n-1),and also excludes 1