LeetCode 1306. 跳跃游戏 III 题目描述 这里有一个非负整数数组 arr ，你一开始处在某个下标 start 处。当你位于下标 i 时，你可以跳到 i + arr[i] 或者 i - arr[i] 。请你判断是否能够跳到 任何 对应元素值为 0 的位置。 注意： 任何时候你都不能跳到数组外。 数组长度范围 [1, 5 * 10^4] ，元素范围 [0, 5 * 10^4] 。 示例 输入：arr = [ 4,2,3,0,3,1,2 ], start = 5 输出：true 解释： 从下标 5 → 4 → 1 → 3 或 5 → 6 → 4 → 1 → 3，都可以到达值为 0 的下标 3。 解题过程 1. 问题分析 从起点 start 出发，每次可以向左或向右跳 arr[i] 步。 目标是到达某个位置 j 使得 arr[j] == 0 。 这是一个 可达性 问题，可以用搜索算法解决。 注意不能越界。 2. 思路选择 每个位置是一个节点，每个节点最多有两个邻居： i + arr[i] 和 i - arr[i] 。 适合用 BFS 或 DFS 遍历所有可达位置。 BFS 可以更快找到最近的 0，但本题只问是否可达，所以 BFS/DFS 均可。 需要记录访问过的位置，避免重复访问和死循环。 3. BFS 详细步骤 初始化队列，将 start 入队。 使用一个 visited 数组（或集合）记录已访问的下标。 循环直到队列为空： 弹出队首元素 i 。 如果 arr[i] == 0 ，返回 true 。 否则，检查 i + arr[i] 和 i - arr[i] 是否在数组范围内且未访问过，若合法则入队并标记已访问。 如果队列空仍未找到 0，返回 false 。 4. 举例说明 arr = [ 4,2,3,0,3,1,2 ], start = 5 初始：队列 [ 5 ]，visited = {5} 5：arr[ 5 ] = 1 → 可跳到 4 和 6 4 入队，visited = {5,4} 6 入队，visited = {5,4,6} 4：arr[ 4 ] = 3 → 可跳到 1 和 7（7 越界，忽略） 1 入队，visited = {5,4,6,1} 6：arr[ 6 ] = 2 → 可跳到 4（已访问）和 8（越界） 1：arr[ 1 ] = 2 → 可跳到 3 和 -1（越界） 3 入队，visited = {5,4,6,1,3} 3：arr[ 3 ] = 0 → 找到 0，返回 true 5. 复杂度分析 时间复杂度 O(n)：每个位置最多访问一次。 空间复杂度 O(n)：队列和 visited 集合的空间。