題目描述

題目描述

小華和小薇一起通過玩積木游戲學習數學。?

他們有很多積木，每個積木塊上都有一個數字，積木塊上的數字可能相同。

小華隨機拿一些積木挨著排成一排，請小薇找到這排積木中數字相同目所處位置最遠的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);}}
}