第一次在LeetCode上看到“跳跃游戏Ⅳ”这道题，我正用go语言刷题刷到接近麻木的状态。题目给了一个整数数组nums，问从索引0出发能不能走到最后一个下标、最少要几步。我一开始以为它跟前面几道跳跃游戏一样，写个贪心或者动态规划就能过，结果越写越发现不对：这题的移动规则里藏着一张“同值跳跃”的大网，走错一步就会掉进O(n²)的复杂度深渊。
后来我把它完整啃下来，才发现表面是跳跃，骨子里是最经典的BFS求无权图最短路，而真正拉开差距的，是那个“值→下标索引表”的处理。无论你是在准备算法面试，还是想用Go把图论BFS练扎实，这篇文章都值得看完。我会把题目建模、索引优化、完整代码、边界测试以及我踩过的坑全部摊开讲，保证你能直接照着复现。
1. 题目理解与模型建立
1.1 完整规则到底在说什么
不同平台对“跳跃游戏Ⅳ”的描述会有细微差别，但更常见的完整规则是这样：给定长度 n 的整数数组 nums，一开始你站在第一个元素（下标0）上，目标是到达最后一个元素（下标n-1）。每一步你可以从当前下标 i 移动到：
- i+1：向右相邻移动；
- i-1：向左相邻移动；
- 任意下标 j，只要 nums[j] == nums[i]：同值自由跳跃。
问：最少需要多少步才能到终点。
注意第三条规则特别关键：它意味着数组里所有值相同的下标，彼此之间都是一张“全连通网”。比如 nums 里有一堆 7，那么任何一个值为7的下标，都可以一步跳到任意另一个值为7的下标。这个特性让题目瞬间从“相邻走路”变成了“图中找最短路”。
而你给的描述里提到“只能向右走、目标位置的值必须满足一定条件”的版本，其实只是把这张图的边集裁剪成“单向边”的特殊情况。无论怎么裁剪，建模思路都不变，我们先把通用版本的解法吃透，变体后面单独说。
1.2 为什么第一反应必须是BFS
先想一个朴素问题：从0出发，每次移动代价都是1步，求到 n-1 的最少步数。这本身就是“无权图最短路”的经典场景，而处理无权图最短路的标准算法就是广度优先搜索BFS。
BFS的核心规律是“按层扩展”：先把起点放进去，然后第一层是所有走一步能到的点，第二层是所有走两步能到的点。由于每一层按顺序推进，某节点第一次被访问时，经过的步数一定是最少的。这是BFS自身性质保证的，不需要额外证明，也不用 Dijkstra 那套带权逻辑。
生活化类比：你从家出发去公司，每次只能打车到相邻路口或者某个和前一个路口同名的小区。出租车每趟都是1分钟。你用手机地图一层层看“1分钟内能到哪、2分钟内能到哪”，第一次刷出公司时那分钟数就是最短时间，因为不存在“更晚出发却更早到达”的绕路魔法。
所以这题不需要贪心猜跳法，也不需要DFS回溯，BFS天然适合。
1.3 变体提醒：向右限制与值条件
如果你拿到的题目描述真的是“只能向右走，且目标下标 j > i，同时目标位置的值必须比当前位更……（更大/更小/相等）”，也不用慌。本质还是那张图，只不过把无向边换成了有向边。
- 只能向右：删掉 i-1 这条边，且同值跳跃也只在 j > i 时成立；
- 目标值还必须满足大小条件：同值自由跳变成“条件跳”，建图时按条件加边。
这种情况下图会退化成有向无环图，理论上动态规划也能做。但BFS仍然成立，只是边集更少，搜索更快。后面第6节我会专门给出变体版的调整思路。先把通用版解决，你对图模型的理解才算真的到位。
2. 核心算法设计
2.1 朴素BFS为什么一定超时
最直接的想法是：BFS每从队列里弹出一个节点 i，就扫描整个 nums，把所有 nums[j] == nums[i] 的下标 j 都加进队列。这个逻辑没有错，错在复杂度。
假设数组长度 n=10万。最坏情况下所有值都相同，那么第一个节点出队时要扫描10万次，把后面所有节点入队；第二个节点出队时又要扫描10万次，再入队一遍；以此类推，总复杂度是 O(n²)，也就是一百亿次操作，在 LeetCode 上铁定超时。
这个问题的根源在于：你把“值”当成线性数组在用，每次都要全表扫描。真正的解法是建索引——这正是题面里“nums、索引”这两个关键词最直接的含义。
2.2 建立“值→下标列表”的索引表
我们在遍历一遍数组时，用一个 map[int][]int 把所有相同值的下标收集到同一个桶里。比如：
nums = [7, 1, 7, 7, 2, 0, 7] 索引表： 7 -> [0, 2, 3, 6] 1 -> [1] 2 -> [4] 0 -> [5]这样当你站在某个下标 i 时，查一下 nums[i] 对应的 bucket，就能瞬间拿到所有同值下标，不需要再满数组乱扫。一次查询的代价近似 O(1)，构建索引表本身只要 O(n)。
这和数据库建索引是同一个道理：MySQL 里如果经常按某个字段做 where 查询，你会给这个字段建索引，避免全表扫描。这里的 map 就是“值字段”上的哈希索引，用空间换时间，把最频繁的查询从 O(n) 压到 O(1)。
2.3 同值组“用完即删”还能不能保证正确
这是全题最重要的优化思想，也是很多人容易忽略的地方。假设你从下标 i 出发，第一次遇到值 v，在 BFS 的某一层把整个 bucket 里所有还没有访问过的下标全部送入队列。那么这些下标的最短距离已经确定了，至少不会比当前层多1步更多。
如果之后又从另一个值同为 v 的下标出发，再次把整个 bucket 展开一遍，会发生什么？那些节点要么已经入队，要么已经有更短的路径被访问过，重复展开拿到的步数只会更大，不可能刷新任何人的最短距离。也就是说，值 v 对应的同值组只需要被展开一次。
因此，在代码里只要遇到某个值第一次出现并完成同值跳跃后，就直接 delete 掉索引表中的这个 key。这个操作让同一个同值组永远不会被第二次遍历，整体复杂度从 O(n²) 降到了 O(n)。
注意一个细节：如果某个值 v 的 bucket 里有节点尚未被访问，第一次展开时它们必然全部入队。所以“第一次展开之后整组信息就用完了”这个结论是成立的，不必担心删早了会丢答案。
2.4 BFS的层数与队列状态管理
我们按层来算步数：每处理完当前层的所有节点，步数加1。这样不需要在每个节点结构体里额外存一个 depth 字段，省内存，也方便直接返回答案。
代码层面的做法是：每一轮开始前，记录当前队列中属于这一层的节点个数 size；只处理这 size 个节点，处理完后步数自增。用这种分层BFS，你在节点弹出时检查它是不是终点，如果是就立刻返回当前的步数。
3. Go实现与代码走读
3.1 数据结构选型
先聊实现细节，因为 Go 刷题的写法跟 C++/Java 差别还挺大。
队列：直接拿切片当队列用。不要用 container/list，链表节点散落内存、缓存不友好，性能反而差。关键是用 head 指针代替出队时的切片删除。如果写 q = q[1:]，每次都会发生底层数组的头部搬运，数据量一大很容易造成额外开销。
visited：用 []bool，长度 n。不要用 map[int]bool，虽然写起来方便，但哈希和扩容开销都不小，在线判题场景容易被常数拖慢。
索引表：用 map[int][]int。构建时给 map 一个初始容量 n，减少 rehash。
3.2 完整可运行代码
func minJumps(arr []int) int { n := len(arr) if n <= 1 { return 0 } // 构建“值 -> 下标列表”的索引表 idxMap := make(map[int][]int, n) for i, v := range arr { idxMap[v] = append(idxMap[v], i) } visited := make([]bool, n) visited[0] = true q := make([]int, 0, n) q = append(q, 0) ans := 0 head := 0 for head < len(q) { size := len(q) - head // 当前层的节点数量 for ; size > 0; size-- { cur := q[head] head++ if cur == n-1 { return ans } // 1. 同值跳跃：使用索引表，用完即删 if positions, ok := idxMap[arr[cur]]; ok { for _, nxt := range positions { if !visited[nxt] { visited[nxt] = true q = append(q, nxt) } } delete(idxMap, arr[cur]) } // 2. 向左相邻跳 if cur-1 >= 0 && !visited[cur-1] { visited[cur-1] = true q = append(q, cur-1) } // 3. 向右相邻跳 if cur+1 < n && !visited[cur+1] { visited[cur+1] = true q = append(q, cur+1) } } ans++ } return -1 }3.3 逐段拆解关键逻辑
先看索引构建：遍历 arr，把同一个值的所有下标 append 到同一个桶里。这里不能优化成只保留“第一个和最后一个下标”，因为中间下标虽然对朴素BFS没用，但在同值跳跃网络里同样是关键节点，必须全量收集。
再看BFS主循环。最容易被忽略的是 head 和 size 的配合：size 计算的是“当前这一层还剩多少个节点”，而不是 len(q)。因为随着同值跳跃，下一层的节点已经不断 append 进 q 了，如果直接用 len(q) 来控制内层循环，就会把下一层节点也在当前步处理完，步数统计就乱了。
delete(idxMap, arr[cur]) 放在所有扩展完成之后。这么做的目的是：cur 可能只是随机踩到某个值，如果它已经不是第一次出现，索引表里早就没有这个 key，delete 自然无事发生；如果是第一次，则整组信息都用完了，立刻删掉，下一轮绝不会重复展开。
相邻跳的顺序其实无所谓，但建议先做同值跳跃再做左右跳，因为同值跳跃能把大量节点一次性入队，让BFS更快触及终点。
3.4 Go实现里容易踩的几个细节
Go 的 map 在 range 遍历过程中 delete 当前 key 是安全的。有人担心“在遍历 positions 时删除 idxMap[arr[cur]] 会污染迭代”，其实不会，因为这里先完成了 positions 的全部遍历，delete 发生在 for 循环之后，没有并发读写。
切片 q 扩容后，head 索引仍然有效。Go 切片扩容会分配新的底层数组，但 head 只是整数下标，下次通过 q[head] 访问到的是新数组里对应位置的元素，完全没问题。
预分配 q 的容量为 n 是个好习惯。虽然极端情况下队列长度不会超过 n，但如果不指定容量，切片会多次扩容并拷贝，白白浪费时间。同理，idxMap 预分配 n 也能减少扩容次数。
4. 正确性论证与边界用例
4.1 BFS为什么保证最短步数
无权图BFS的“首次访问即最短”性质，是这道题的底气。BFS按层扩展，假设某个节点 x 第一次被访问时经过的路径不是最短，那它一定存在一条更短的路径。由于图是单位权边，更短意味着更早的层，可如果更早层就能访问到 x，x 必然在那一层被入队，就不会出现“更晚才发现”的情况。矛盾，因此第一次访问就是最短。
这个性质要求我们在代码里严格保证 visited 只在首次入队时设置。一旦节点入队，后面任何路径想再入队都会被 visited 挡掉。这样队列里每个节点只可能出现一次。
4.2 删除同值索引的数学保证
再往深里想一层：为什么删索引不丢解？
设值 v 的同值组为集合 S。第一次访问到 S 中任何一个节点时，BFS 会把 S 中所有未访问节点全部以“当前层步数+1”送入队列。也就是说，从这次开始，S 中所有节点都已经有了一个明确的最短距离上界 d。在之后的任意时刻，如果又从某个 S 内节点出发，复读一遍同值跳跃，得到的距离只会是 d+1、d+2 之类更大的值，不可能小于已有的 d（或者 d-1 之类的更小距离早已存在）。
所以，一个同值组至多有一个“值得展开的时机”，就是它第一次被访问的时机。delete 掉这个组，不仅正确，而且是精算到极限的优化。这个证明在面试时能讲清楚，比直接背套路强一百倍。
4.3 特殊输入怎么处理
n==1：起点就是终点，直接返回0。
全数组所有值都相同：当起点0出队时，索引表里包含 0 到 n-1 全部下标。同值跳跃会把 n-1 直接入队，下一轮处理到 n-1 时返回 ans=1。也就是说，全同值数组最少只需要1步，因为可以从下标0一步跳到任意同值下标。
所有值互不相同：同值组全部是单元素，同值跳跃退化为“跳到自身”，没有意义。此时问题退化成只能左右相邻移动，最坏情况需要 n-1 步。
数组中含有 0、负数、大整数：map 的 key 类型是 int，完全兼容，不需要额外处理。
因为有 i+1 这条边，图一定是连通的，所以理论上不会出现不可达。代码里的 return -1 只是兜底，正常流程一定会在队列耗尽前返回正确步数。
4.4 复杂度到底是多少
时间上，每个下标最多入队一次、出队一次，处理一次的代价是：查索引表 O(1)，把同值组遍历一遍。每个下标只会出现在它所属的同值组里，且由于组被删除，所有同值组遍历总次数不超过 n。因此总时间复杂度 O(n)。
空间上，索引表存了所有下标，visited 长度 n，队列长度不超过 n，总空间 O(n)。
也就是说，这个算法在线性规模内解决问题，10万、20万的数组都能轻松跑过。
5. 常见错误与排查实录
5.1 忘记删除索引，全同值数组直接TLE
我第一次提交时就忘了 delete。自测小用例能过，一丢到全同值的大数组上，运行时间直接爆炸。原因很简单：第一个节点把整组都入队了，后面的节点出队时又重复遍历整组，每个节点都重复一轮 O(n) 扫描，最后整体 O(n²)。
排查方法很简单：在 delete 那个分支里加一个计数器，看同值展开执行了多少次。如果展开次数远大于不同值的数量，说明索引没删干净。
5.2 用数组扫描代替真实索引
还有一个典型错法：不在预处理阶段建索引，而是每次出队时写一个内层循环去扫 nums，找所有同值下标。这样写出来的代码看起来非常“朴素正确”，但复杂度跟不建索引完全一样，还是 O(n²)。我刚开始学BFS时就干过这事，本地跑小数据没问题，拿到服务器上大数据就傻眼。
正确的检查标准是：预处理之外，是否还有按值扫描数组的代码。如果有，就是索引没建好。
5.3 visited做成了map导致常数过大
有人会用 map[int]bool 来做访问标记，然后每次判断 visited[nxt] 是否存在。这在功能上没毛病，但 map 的哈希开销比 bool 切片高得多。当 n 到10万以上时，这个常数差距足够造成超时或者逼近超时边缘。正确做法是 make([]bool, n)，直接用下标索引，O(1) 且没有哈希成本。
对应地，队列也不要搞成 [][]int 这种二维结构，每次 append 一个包含下标和步数的结构体，内存和效率都更差。用 head 指针维护一层层扫描，才是刷题圈的常规姿势。
5.4 层数统计方式写错
如果不用 size 捕获当前层，而在内层循环里直接用 len(q) 判断，就会出现“把下一层节点也在本轮处理完”的bug。最典型的症状是：返回的步数比正确答案小，尤其是链条式的输入下非常明显。
排查时可以在每轮开始打印 cur 和 ans，看是否出现了“当前层还没处理完，ans 已经加了好几次”的情况。
5.5 对拍测试是最可靠的自检手段
我自己写算法题的经验是：不要只盯着“能不能过样例”，一定要写一个慢但逻辑简单的朴素BFS来对拍。朴素版不删除索引，也不做任何优化，每次扫描全数组找同值点，保证正确性。然后随机生成大量小数组，让优化版和朴素版跑同样的输入，比对结果。
随机用例生成时要注意覆盖这些结构：长度1的数组、长度2的数组、全相同值、值互不相同、值只在局部重复、包含负数和零。只要对拍一万组结果全一致，基本可以放心提交。
6. 把“建索引”的思路迁移到其他场景
6.1 从数组索引到数据库索引
这道题里那个 map[int][]int，本质上就是一张哈希索引表。你跟别人聊 MySQL 的时候会发现同样的道理：where 条件里经常要查的某个字段，如果每次都全表扫描，数据量一大就崩；给这个字段建索引后，查询就能直接定位到目标记录的位置列表。
所以面试时如果有人问你“数据库索引为什么快”，你可以用这个题当例子：查询模式固定且高频时，用额外的存储空间维护“值→位置”的映射，把查找从 O(n) 降到近似 O(1) 或 O(log n)。同理，“where 条件 a and b 应该怎么建索引”这类问题的核心，是先分析查询会不会同时命中多个条件、哪个条件过滤性更强，再决定联合索引的字段顺序。跳跃游戏Ⅳ里的索引构建也是同样的取舍逻辑。
6.2 如果题目变成“只能向右跳”的变体
假设题面真的限定“只能向右走，且目标位置的值必须满足一定条件”，我们的边集会发生变化：
- 删除 i-1 的向左跳；
- 同值跳跃变成从 i 跳到满足 j > i 且值符合条件的 j；
- 如果值要求递增，那图一定无环，可以按动态规划或贪心做，但BFS同样可行，只是边更少、队列更短。
建索引的思路依然有效：提前把每个值的所有下标存下来，每次需要找“右边第一个/所有满足条件的下标”时，用二分或者直接遍历该值的下标列表即可，不需要重新扫描整个数组。这其实是很多“向右跳”类型题的标准优化套路。
6.3 BFS模型还可以扩展到更多状态
如果以后碰到状态不只是“下标”，还包括“剩余步数”“当前速度”之类，BFS的图节点就要从一维数组扩展成多维状态。但骨架不会变：先把状态转移摸清，把可转移目标做成索引或预计算表，再一层层BFS。这个思维习惯养成了，刷题的上限会高很多。
最后再分享一个我的实战习惯：任何“数组+最少步数”的题，拿到手先别急着写代码，先在纸上画几个小输入的图，把每种移动方式当成一条边标出来。只要图模型画对了，后面用什么语言实现都是水到渠成的事。Go 刷题还有个额外好处，就是能逼你把内存管理这种底层习惯练好，head 指针队列、bool 切片这些写法，换个项目照样用得上。
