题目描述
LeetCode 1306 — 跳跃游戏 III (Medium)
给定一个非负整数数组 arr，你最初位于 start 位置。当你位于下标 i 时，可以跳到：
i + arr[i]（向右跳）i - arr[i]（向左跳）
请判断是否能到达任意值为 0 的位置。注意，任何情况下都不能跳出数组。
示例 1：
- 输入：
arr = [4,2,3,0,3,1,2], start = 5 - 输出：
true - 解释：路径
5 → 4 → 1 → 3，arr[3] = 0✓
下标 5 值为 1，只能跳到 4 或 6；选择跳到 4（值为 3），再跳到 1（值为 2），再跳到 3（值为 0），到达目标。
示例 2：
- 输入：
arr = [4,2,3,0,3,1,2], start = 0 - 输出：
true - 解释：路径
0 → 4 → 1 → 3，arr[3] = 0✓
示例 3：
- 输入：
arr = [3,0,2,1,2], start = 2 - 输出：
false - 解释：从下标 2 出发，只能到达下标 0 和下标 4，均无法到达值为 0 的下标 1。
约束：
1 <= arr.length <= 5 * 10^40 <= arr[i] < arr.length0 <= start < arr.length
核心思路：数组即图
初看是一个数组问题，但本质是图遍历——每个下标是一个节点，下标 i 到 i + arr[i] 和 i - arr[i] 是两条有向边。问题转化为：
从
start节点出发，能否走到任意一个值为0的节点？
既然抽象成了图，BFS 和 DFS 都可以做。两者的核心组件相同：
- visited 数组：标记已访问节点，避免重复遍历甚至死循环
- 边界检查：跳转目标必须在
[0, arr.length)范围内 - 终止条件：到达值为
0的位置
BFS 逐层展开，适合找最短路径；DFS 一路走到底，代码更简洁。本题只需判断可达性，两者均可。
解法一：BFS
维护一个队列，每次取出队首节点，检查它的两个跳转目标：若合法且未访问过，入队并标记已访问。循环直到队列为空或找到值为 0 的位置。
bool canReach(vector<int>& arr, int start) {
queue<int> q;
vector<bool> visited(arr.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int idx = q.front();
q.pop();
// 当前节点值即为 0，直接返回
if (arr[idx] == 0) {
return true;
}
// 两个跳转方向
int left = idx - arr[idx];
int right = idx + arr[idx];
if (left >= 0 && !visited[left]) {
if (arr[left] == 0) return true;
q.push(left);
visited[left] = true;
}
if (right < (int)arr.size() && !visited[right]) {
if (arr[right] == 0) return true;
q.push(right);
visited[right] = true;
}
}
return false;
}
复杂度：
- 时间 O(n)：每个节点最多入队一次
- 空间 O(n)：队列 + visited 数组
解法二：DFS
从 start 出发，递归地向两个方向深入。同样用 visited 数组避免重复访问。
bool dfs(vector<int>& arr, vector<bool>& visited, int idx) {
// 越界或已访问
if (idx < 0 || idx >= (int)arr.size() || visited[idx]) {
return false;
}
// 到达目标
if (arr[idx] == 0) {
return true;
}
visited[idx] = true;
// 向两个方向递归，任一方向找到即可
return dfs(arr, visited, idx + arr[idx])
|| dfs(arr, visited, idx - arr[idx]);
}
bool canReach(vector<int>& arr, int start) {
vector<bool> visited(arr.size(), false);
return dfs(arr, visited, start);
}
递归展开（同上例 start = 5）：
dfs(5) → visited[5]=T
├─ dfs(4) → visited[4]=T
│ ├─ dfs(7) → 越界, false
│ └─ dfs(1) → visited[1]=T
│ ├─ dfs(3) → arr[3]==0 → true ✓
│ └─ (短路，不再执行 dfs(-1))
└─ (短路，不再执行 dfs(6))
复杂度： 同 BFS，时间 O(n)，空间 O(n)（递归栈深度最坏 O(n)）。
BFS vs DFS 对比
| BFS | DFS | |
|---|---|---|
| 遍历方式 | 逐层展开，队列 | 深度优先，递归/栈 |
| 找最短路径 | ✅ 天然支持（先找到的路径最短） | ❌ 不保证 |
| 空间 | O(n) 队列 | O(n) 递归栈 |
| 代码量 | 稍多 | 更简洁 |
| 适用场景 | 最短距离问题 | 可达性判断、路径搜索 |
本题只判断可达性，两种方法没有优劣之分。但若题目追问「最少跳跃次数」，BFS 天然给出答案——第一次找到 0 时所处的层数即为最短步数。
BFS 求最短跳跃次数
在原 BFS 基础上稍作改动，层序遍历即可得到最少步数：
int minJumps(vector<int>& arr, int start) {
if (arr[start] == 0) return 0;
queue<int> q;
vector<bool> visited(arr.size(), false);
q.push(start);
visited[start] = true;
int steps = 0;
while (!q.empty()) {
int size = q.size();
steps++;
for (int i = 0; i < size; i++) {
int idx = q.front();
q.pop();
for (int next : {idx + arr[idx], idx - arr[idx]}) {
if (next < 0 || next >= (int)arr.size() || visited[next]) {
continue;
}
if (arr[next] == 0) return steps;
q.push(next);
visited[next] = true;
}
}
}
return -1; // 无法到达
}