第一次在LeetCode上看到“跳跃游戏Ⅳ”这道题我正用go语言刷题刷到接近麻木的状态。题目给了一个整数数组nums问从索引0出发能不能走到最后一个下标、最少要几步。我一开始以为它跟前面几道跳跃游戏一样写个贪心或者动态规划就能过结果越写越发现不对这题的移动规则里藏着一张“同值跳跃”的大网走错一步就会掉进O(n²)的复杂度深渊。后来我把它完整啃下来才发现表面是跳跃骨子里是最经典的BFS求无权图最短路而真正拉开差距的是那个“值→下标索引表”的处理。无论你是在准备算法面试还是想用Go把图论BFS练扎实这篇文章都值得看完。我会把题目建模、索引优化、完整代码、边界测试以及我踩过的坑全部摊开讲保证你能直接照着复现。1. 题目理解与模型建立1.1 完整规则到底在说什么不同平台对“跳跃游戏Ⅳ”的描述会有细微差别但更常见的完整规则是这样给定长度 n 的整数数组 nums一开始你站在第一个元素下标0上目标是到达最后一个元素下标n-1。每一步你可以从当前下标 i 移动到i1向右相邻移动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 都加进队列。这个逻辑没有错错在复杂度。假设数组长度 n10万。最坏情况下所有值都相同那么第一个节点出队时要扫描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 cur1 n !visited[cur1] { visited[cur1] true q append(q, cur1) } } ans } return -1 }3.3 逐段拆解关键逻辑先看索引构建遍历 arr把同一个值的所有下标 append 到同一个桶里。这里不能优化成只保留“第一个和最后一个下标”因为中间下标虽然对朴素BFS没用但在同值跳跃网络里同样是关键节点必须全量收集。再看BFS主循环。最容易被忽略的是 head 和 size 的配合size 计算的是“当前这一层还剩多少个节点”而不是 len(q)。因为随着同值跳跃下一层的节点已经不断 append 进 q 了如果直接用 len(q) 来控制内层循环就会把下一层节点也在当前步处理完步数统计就乱了。delete(idxMap, arr[cur]) 放在所有扩展完成之后。这么做的目的是cur 可能只是随机踩到某个值如果它已经不是第一次出现索引表里早就没有这个 keydelete 自然无事发生如果是第一次则整组信息都用完了立刻删掉下一轮绝不会重复展开。相邻跳的顺序其实无所谓但建议先做同值跳跃再做左右跳因为同值跳跃能把大量节点一次性入队让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 第一次被访问时经过的路径不是最短那它一定存在一条更短的路径。由于图是单位权边更短意味着更早的层可如果更早层就能访问到 xx 必然在那一层被入队就不会出现“更晚才发现”的情况。矛盾因此第一次访问就是最短。这个性质要求我们在代码里严格保证 visited 只在首次入队时设置。一旦节点入队后面任何路径想再入队都会被 visited 挡掉。这样队列里每个节点只可能出现一次。4.2 删除同值索引的数学保证再往深里想一层为什么删索引不丢解设值 v 的同值组为集合 S。第一次访问到 S 中任何一个节点时BFS 会把 S 中所有未访问节点全部以“当前层步数1”送入队列。也就是说从这次开始S 中所有节点都已经有了一个明确的最短距离上界 d。在之后的任意时刻如果又从某个 S 内节点出发复读一遍同值跳跃得到的距离只会是 d1、d2 之类更大的值不可能小于已有的 d或者 d-1 之类的更小距离早已存在。所以一个同值组至多有一个“值得展开的时机”就是它第一次被访问的时机。delete 掉这个组不仅正确而且是精算到极限的优化。这个证明在面试时能讲清楚比直接背套路强一百倍。4.3 特殊输入怎么处理n1起点就是终点直接返回0。全数组所有值都相同当起点0出队时索引表里包含 0 到 n-1 全部下标。同值跳跃会把 n-1 直接入队下一轮处理到 n-1 时返回 ans1。也就是说全同值数组最少只需要1步因为可以从下标0一步跳到任意同值下标。所有值互不相同同值组全部是单元素同值跳跃退化为“跳到自身”没有意义。此时问题退化成只能左右相邻移动最坏情况需要 n-1 步。数组中含有 0、负数、大整数map 的 key 类型是 int完全兼容不需要额外处理。因为有 i1 这条边图一定是连通的所以理论上不会出现不可达。代码里的 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 切片这些写法换个项目照样用得上。