数组跳跃问题求解：计算跳出数组所需的跳跃次数

问题描述 #

给定一个包含N个整数的数组A，数组中每个元素可视为指向其他元素的指针：若A[K] = M，则当前位于索引K时，会跳转到索引K + M对应的元素。跳跃规则如下：

1. 初始位置为数组的第0个元素（索引0）
2. 每次跳跃从当前索引的元素，移动到它指向的目标索引位置
3. 过程中可能出现无限循环（始终无法跳出数组）或直接跳出数组的情况

需要编写函数，输入数组A后，返回跳出数组所需的跳跃次数；若陷入无限循环，则返回-1。

解决思路 #

要解决这个问题，核心需要处理两个关键点：

• 准确计算每次跳跃后的位置，判断是否跳出数组边界
• 检测循环（避免无限执行）：如果某次跳跃后的位置是之前已经访问过的索引，说明会陷入循环，永远无法跳出数组

具体步骤：

1. 初始化当前索引为0，跳跃次数为0，用集合记录已访问过的索引
2. 循环执行以下操作：
   • 若当前索引已在访问集合中，返回-1（陷入循环）
   • 将当前索引加入访问集合
   • 计算下一个索引：当前索引 + A[当前索引]
   • 跳跃次数加1
   • 判断下一个索引是否超出数组范围（小于0 或 大于等于数组长度）：若是则返回当前跳跃次数
   • 否则将当前索引更新为下一个索引，继续循环

代码实现（Python） #

def jump_out_count(A):
    array_length = len(A)
    visited_indices = set()
    current_idx = 0
    jump_times = 0

    while 0 <= current_idx < array_length:
        # 检测循环：当前索引已访问过，说明陷入无限跳跃
        if current_idx in visited_indices:
            return -1
        
        visited_indices.add(current_idx)
        # 计算下一个跳跃的索引
        next_idx = current_idx + A[current_idx]
        jump_times += 1

        # 判断是否跳出数组
        if next_idx < 0 or next_idx >= array_length:
            return jump_times
        
        current_idx = next_idx
    
    # 极端情况：初始索引就不在数组范围内（题目中初始为A[0]，此情况一般不会触发）
    return 0

测试示例 #

• 示例1：输入A = [2, -1, 1, 2, 3]
  跳跃过程：0 → 2 → 3 → 5（超出数组长度5），共3次跳跃，返回3
• 示例2：输入A = [1, -1]
  跳跃过程：0 → 1 → 0（已访问过），陷入循环，返回-1
• 示例3：输入A = [-3, 1, 2]
  初始索引0，计算下一个索引为0 + (-3) = -3（小于0），直接跳出，返回1

注意事项 #

• 数组元素可以是负数，需处理向左跳跃跳出数组左边界的情况
• 必须使用集合记录已访问索引，否则会因循环导致程序死循环
• 边界判断要同时覆盖数组的左（<0）和右（>=数组长度）边界

内容的提问来源于stack exchange，提问作者Max