目标
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
- i + 1 需满足：i + 1 < arr.length
- i - 1 需满足：i - 1 >= 0
- j 需满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。示例 2：
输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。示例 3：
输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。说明：
- 1 <= arr.length <= 5 * 10^4
- -10^8 <= arr[i] <= 10^8
思路
有一个数组 nums，从下标 0 开始移动，目标是到达下标 n - 1。每次移动可以移动到相邻的位置，或者满足 nums[j] == nums[i] 的位置 j。返回最少移动次数。
与 3629.通过质数传送到达终点的最少跳跃次数 类似，那个题目质数列表的处理比这个相同元素列表稍微复杂一些。
思路都是 BFS，从起点出发将下一个可以到达的节点加入队列，直到到达终点。关键点是处理完一次相同元素下标列表之后要清空，避免重复访问。
小优化：只取相同元素的首尾下标。
代码
/**
* @date 2026-05-18 8:59
*/
public class MinJumps1345 {
public int minJumps_v1(int[] arr) {
int n = arr.length;
Map<Integer, List<Integer>> map = new HashMap<>();
int i = 0;
while (i < n) {
int start = i;
while (i < n && arr[i] == arr[start]) {
i++;
}
map.computeIfAbsent(arr[start], x -> new ArrayList<>()).add(start);
if (start != i - 1) {
map.get(arr[start]).add(i - 1);
}
}
List<Integer> q = new ArrayList<>();
q.add(0);
boolean[] visited = new boolean[n];
int res = 0;
while (!q.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for (Integer cur : q) {
if (cur == n - 1) {
return res;
}
if (cur > 0 && !visited[cur - 1]) {
visited[cur - 1] = true;
tmp.add(cur - 1);
}
if (!visited[cur + 1]){
visited[cur + 1] = true;
tmp.add(cur + 1);
}
if (map.get(arr[cur]) != null) {
for (Integer index : map.get(arr[cur])) {
if (!visited[index]){
visited[index] = true;
tmp.add(index);
}
}
map.remove(arr[cur]);
}
}
q = tmp;
res++;
}
return res;
}
}
性能
