相同数字的积木游戏

题目描述

题目描述

小华和小薇一起通过玩积木游戏学习数学。 

他们有很多积木，每个积木块上都有一个数字，积木块上的数字可能相同。

小华随机拿一些积木挨着排成一排，请小薇找到这排积木中数字相同目所处位置最远的2块积木块，计算他们的距离。 

小薇请你帮忙替她解决这个问题。

输入

第一行输入为N，表示小华排成一排的积大总数。 

接下来 N 行每行一个数字，表示小花排成一排的积大上数字。

输出

相同数字的积木的位置最远距离; 

如果所有积木数字都不相同，请返回 -1

样例输入

5
1
2
3
1
4

样例输出

3

解题思路

        从题目描述得知，我们首先需要确定众多积木中有没有数字相同的积木，若没有数字相同的积木，直接输出-1即可；若有数字相同的积木，再进行后续操作。

        通过将数组中的元素存到HashMap中，key值代表元素，value值代表元素出现次数。若哈希表的大小和数组大小相同，则说明数组内每个元素都只出现了1次，没有相同数字的积木。否则，双指针遍历数组，找到相同数字的距离，取最大值。

AC代码

import java.util.HashMap;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] arr = new int[N];int max = 0;int begin = 0;int end = 0;HashMap<Integer, Integer> hashMap = new HashMap<>();for (int i=0;i<N;i++){arr[i] = sc.nextInt();if (!hashMap.containsKey(arr[i])){hashMap.put(arr[i],1);}else {hashMap.put(arr[i], hashMap.get(arr[i]) +1 );}}//若哈希表的长度 和 数组长度 相等，则说明数组内每个元素都只出现了1次，没有相同数字的积木。if (hashMap.size() == arr.length){System.out.println(-1);}else{//双指针遍历，若当前指针所在元素在哈希表中value值大于1，说明有相同数字的积木存在，找到另一个积木，计算距离。for (int i=0;i<N;i++){if (hashMap.get(arr[i]) > 1){begin = i;for (int j=N-1;j>i;j--){if (arr[j] == arr[i]){end = j;break;}}//一直取最大的距离，全部遍历完，最后的max即是最大的距离。max = Math.max(max,end - begin);}}System.out.println(max);}}
}