题目描述
LeetCode 1345 — 跳跃游戏 IV (Hard)
给定一个整数数组 arr，你最初位于数组的第一个下标（下标 0）。每一步，你可以从下标 i 跳到：
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 - 解释：路径
0 → 4 → 3 → 9，下标 9 是最后一个下标。
下标 0 值为 100，跳到同为 100 的下标 4；再跳到前一个相邻下标 3（值为 404）；再跳到同为 404 的下标 9，到达终点。
示例 2：
- 输入：
arr = [7] - 输出：
0 - 解释：起始就在最后一个下标，无需跳跃。
示例 3：
- 输入：
arr = [7,6,9,6,9,6,9,7] - 输出：
1 - 解释：下标 0 值为 7，下标 7 值也为 7，直接跳过去即可。
约束：
1 <= arr.length <= 5 * 10^4-10^8 <= arr[i] <= 10^8
核心思路：无权图最短路径
问题建模
与 1306（跳跃游戏 III）不同，本题不仅要求判断可达性，还要求最少步数。这立刻指向 BFS——在无权图中，BFS 天然保证首次到达目标时路径最短。
将问题建模为图：
- 节点：数组的每个下标
- 边：三种跳转 — 相邻（
i±1） + 同值（所有满足arr[i] == arr[j]的j） - 边权：均为 1，属于无权图
于是问题转化为：从节点 0 出发，到达节点 n-1 的最短距离。
关键优化：为什么必须清除同值映射
如果只是简单 BFS，直接对所有同值下标遍历入队即可。但考虑最坏情况——所有元素值相同，例如 arr = [7, 7, 7, ..., 7]（长度 10^4）：
- 第一个节点 0 入队时，会遍历所有 n 个同值下标，全部入队
- 第二个节点 1 出队时，又遍历所有 n 个同值下标——但它们都已经访问过
如果不加控制，每次出队都扫描整个同值列表，时间复杂度会退化到 O(n²)。这在 n = 5 × 10^4 的约束下不可接受。
核心技巧：处理完某个值的所有下标后，立即清空该值在哈希表中的映射。 这样一来，每个值的同值列表最多被遍历一次，总遍历次数为 O(n)。
为什么清空是安全的？ 因为 BFS 保证首次访问某个节点时距离最短。一旦某个值的所有下标被遍历并标记 visited 后入队，后续再遇到同值的节点无需再次遍历——此时同值列表已被清空，自动跳过。
哈希表
hash map 的 O(1) 查找和 O(1) 清空是这道题的核心。数组元素取值范围是 [-10^8, 10^8]，不能直接用数组下标索引。而 unordered_map 提供了：
- O(1) 定位同值列表：给定
arr[cur]，瞬间拿到所有等值下标 - O(1) 清空：
clear()操作直接将列表置空，已访问的值不再产生遍历开销 - 空间高效：只存储实际出现的值，不浪费内存
如果用 map（红黑树），查找 O(log n) 虽可接受，但 clear() 后节点仍需从树中移除，操作更重。unordered_map 的 bucket + clear 在此场景下是最优选择。
解法：BFS + 哈希表
算法分为三个阶段：
- 预处理：用
unordered_map<int, vector<int>>将所有下标按值分组 - BFS 层序遍历：队列中存储下标，逐层处理，记录步数
- 出队处理：检查
i±1相邻节点 + 遍历同值列表，访问后清空同值列表
int minJumps(vector<int>& arr) {
int n = arr.size();
if (n == 1) return 0; // 已在终点
// 哈希表初始化
unordered_map<int, vector<int>> valToIndices;
for (int i = 0; i < n; i++) {
valToIndices[arr[i]].push_back(i);
}
vector<bool> visited(n, false);
queue<int> q;
q.push(0);
visited[0] = true;
int steps = 0;
while (!q.empty()) {
int size = q.size(); // 当前层的节点数
for (int i = 0; i < size; i++) {
int cur = q.front();
q.pop();
// 到达终点
if (cur == n - 1) return steps;
// 相邻跳转：i+1
if (cur + 1 < n && !visited[cur + 1]) {
visited[cur + 1] = true;
q.push(cur + 1);
}
// 相邻跳转：i-1
if (cur - 1 >= 0 && !visited[cur - 1]) {
visited[cur - 1] = true;
q.push(cur - 1);
}
// 同值跳转：遍历所有等值未访问节点
for (int next : valToIndices[arr[cur]]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
// 清空同值列表，避免重复遍历
valToIndices[arr[cur]].clear();
}
steps++;
}
return -1;
}
复杂度： 时间 O(n)，空间 O(n)。每个节点最多入队一次，每个值列表最多遍历一次。