题目描述
思路解析动画文字版
记住「下标当节点、i±arr[i] 是两条边、seen 防重、BFS 找值为 0 的下标」,下面逐帧套它。
从起点下标 5(紫)出发:标记为已访问(蓝)、放进队列。目标是落到某个值为 0 的下标——这张数组里 arr[3]=0,就是我们要找的终点。
队首弹出下标 5(紫),值 arr[5] = 1,不是 0。看它能往两个方向跳:向右 5 + 1,向左 5 − 1。
先算向右的落点:5 + 1 = 6。再看下标 6 能不能落脚。
下标 6 在界内、还没访问过:标记为已访问(蓝),放进队列队尾,等轮到它再展开它的两个跳法。
先算向左的落点:5 − 1 = 4。再看下标 4 能不能落脚。
下标 4 在界内、还没访问过:标记为已访问(蓝),放进队列队尾,等轮到它再展开它的两个跳法。
队首弹出下标 6(紫),值 arr[6] = 2,不是 0。看它能往两个方向跳:向右 6 + 2,向左 6 − 2。
先算向右的落点:6 + 2 = 8。再看下标 8 能不能落脚。
下标 8 超出了数组范围 0 到 6,这一跳跳出界了,放弃这个方向。
先算向左的落点:6 − 2 = 4。再看下标 4 能不能落脚。
下标 4(蓝)之前已经访问过了,BFS 不重复入队、直接跳过 —— 这正是 seen 数组的作用:挡住「跳过去又跳回来」的死循环。
队首弹出下标 4(紫),值 arr[4] = 3,不是 0。看它能往两个方向跳:向右 4 + 3,向左 4 − 3。
先算向右的落点:4 + 3 = 7。再看下标 7 能不能落脚。
下标 7 超出了数组范围 0 到 6,这一跳跳出界了,放弃这个方向。
先算向左的落点:4 − 3 = 1。再看下标 1 能不能落脚。
下标 1 在界内、还没访问过:标记为已访问(蓝),放进队列队尾,等轮到它再展开它的两个跳法。
队首弹出下标 1(紫),值 arr[1] = 2,不是 0。看它能往两个方向跳:向右 1 + 2,向左 1 − 2。
先算向右的落点:1 + 2 = 3。再看下标 3 能不能落脚。
下标 3 在界内、还没访问过:标记为已访问(蓝),放进队列队尾,等轮到它再展开它的两个跳法。
先算向左的落点:1 − 2 = -1。再看下标 -1 能不能落脚。
下标 -1 超出了数组范围 0 到 6,这一跳跳出界了,放弃这个方向。
队首弹出下标 3(绿):它的值 arr[3] = 0 —— 命中目标!BFS 成功跳到了值为 0 的下标,答案 true。
边界:起点值即 0 直接 true;跳不到则队列耗尽返回 false。
两个追问:判可达 BFS/DFS 皆可;要最短跳数则必须 BFS 按层。
参考代码
from typing import Listfrom collections import dequeclass Solution: def canReach(self, arr: List[int], start: int) -> bool: n = len(arr) seen = [False] * n q = deque([start]) seen[start] = True while q: i = q.popleft() if arr[i] == 0: return True for j in (i + arr[i], i - arr[i]): if 0 <= j < n and not seen[j]: seen[j] = True q.append(j) return False复杂度
- 时间：O(n)，每个下标最多入队一次(seen 挡住重复),出队后只做常数次工作(看两个落点),共 O(n)
- 空间：O(n)，seen 数组 O(n),队列最坏也装 O(n) 个下标
易错点
面试追问把动画讲成自己的话
追问这题用 BFS 还是 DFS?有区别吗?
追问如果改成「最少跳几次才能到值为 0 的下标」呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
连通网络的操作次数
LeetCode 1319 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题