Leetcode刷题100天—447. 回旋镖的数量( 哈希表)—day37

偏执的太偏执、 2022-08-28 08:58 164阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210913135129838][]

#### [447. 回旋镖的数量][447.] ####

难度中等176收藏分享切换为英文接收动态反馈

给定平面上 `n` 对 **互不相同** 的点 `points` ，其中 `points[i] = [xi, yi]` 。**回旋镖** 是由点 `(i, j, k)` 表示的元组 ，其中 `i` 和 `j` 之间的距离和 `i` 和 `k` 之间的距离相等（**需要考虑元组的顺序**）。

返回平面上所有回旋镖的数量。

**示例 1：**

输入：points = [[0,0],[1,0],[2,0]]
    输出：2
    解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

**示例 2：**

输入：points = [[1,1],[2,2],[3,3]]
    输出：2

**示例 3：**

输入：points = [[1,1]]
    输出：0

**提示：**

*  `n == points.length`
 *  `1 <= n <= 500`
 *  `points[i].length == 2`
 *  `-104 <= xi, yi <= 104`
 *  所有点都 **互不相同**

package 哈希表;
    
    import java.util.HashMap;
    import java.util.Map;
    
    /* * https://leetcode-cn.com/problems/number-of-boomerangs/ * 解题思路： * 1. 一个个点遍历，通过两点之间确定距离公式k^2=(y1-x1)^2+(x1-x2)^2获取距离 * 2. 通过哈希遍历保存每两个点的距离，要是相同就加一 * 3. 在遍历哈希获取每个距离统计的次数n,通过公式n(n-1)获取排列次数 */
    public class _447_回旋镖的数量 { 
        public int numberOfBoomerangs(int[][] points) { 
    // 定义一个返回值
        	int sum=0;
    // 遍历每一个点
        	for(int i=0;i<points.length;i++) { 
    // 将每两个点的距离存入哈希.相同的距离就加一
    // 设置哈希
    			HashMap<Integer, Integer> map=new HashMap<>();
        		for(int j=0;j<points.length;j++) { 
    
    // 获取距离
        			int distance=(points[i][0]-points[j][0])*(points[i][0]-points[j][0])
        					+(points[i][1]-points[j][1])*(points[i][1]-points[j][1]);
    // 存入哈希
        			map.put(distance, map.getOrDefault(distance, 0)+1);
        		}
        		System.out.print(map);
    // 遍历完后就开始遍历哈希,因为已经知道每个j点跟i点距离的次数了，获取这些j点的排雷顺序就可以了
            	for(Map.Entry<Integer, Integer> entry:map.entrySet()) { 
            		int value=entry.getValue();
    // 如果更i点距离相同的次数大于1就能排序
            		if (value>1) { 
    					sum+=value*(value-1);
    				}
            	}
        	}
    
        	return sum;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210913135129838]: /images/20220828/38f63d9b57844601a392397dd3d7d787.png
[447.]: https://leetcode-cn.com/problems/number-of-boomerangs/