LeetCode跳跃游戏II：while循环无法终止问题排查求助

问题描述 #

给定一个长度为n的0索引整数数组nums，初始位置为nums[0]。每个元素nums[i]表示从索引i出发的最大向前跳跃长度，即若位于nums[i]，可跳至任意nums[i+j]，其中0≤j≤nums[i]且i+j<n。要求返回到达nums[n-1]的最少跳跃次数，测试用例保证可到达终点。

示例1：输入nums = [2,3,1,1,4]，输出：2
解释：到达最后索引的最少跳跃次数是2。从索引0跳1步到1，再跳3步到最后索引。

示例2：输入nums = [2,3,0,1,4]，输出：2

我的解法 #

class Solution:
    def jump(self, nums: List[int]) -> int:
        
        j = len(nums)-1
        res = []
        while j >= 0:
            cursor = j

            valid_j = j # this variable will hold the best value of j to be set
            while cursor >= 0:
                if nums[cursor] + cursor >= j:
                    valid_j = cursor
                cursor-=1
            
            res.append(valid_j)
            
            j = valid_j

        return len(res)

这段代码存在某个while循环无法终止的问题，导致时间超限，我找不到错误原因，请求帮忙解释。

错误原因分析 #

你的代码逻辑是从终点倒推找能跳到当前位置的最左起点，再更新j为该起点，直到回到索引0。但核心问题出在外层循环的终止条件：

• 当j被更新为0后，外层循环条件j >=0依然成立，会再次进入循环。此时内层循环遍历后，valid_j还是0，j被重新赋值为0，导致无限循环，最终触发时间超限。
• 另外，即使解决死循环，你的算法时间复杂度是O(n²)，面对大长度数组（比如10^4级别的测试用例）时，重复遍历的开销也会导致超时。

修复方案 #

1. 修复死循环的倒推版本

把外层循环条件改为j > 0，当j已经是起点0时直接终止循环：

class Solution:
    def jump(self, nums: List[int]) -> int:
        j = len(nums)-1
        res = 0
        while j > 0:
            valid_j = j
            cursor = j - 1
            while cursor >= 0:
                if nums[cursor] + cursor >= j:
                    valid_j = cursor
                cursor -= 1
            j = valid_j
            res += 1
        return res

2. 更高效的贪心版本（O(n)时间复杂度）

正向遍历数组，维护当前跳跃的边界和能到达的最远位置，每到达边界就增加跳跃次数，避免重复遍历：

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        jumps = 0
        current_end = 0
        farthest = 0
        for i in range(len(nums)-1):
            farthest = max(farthest, i + nums[i])
            if i == current_end:
                jumps +=1
                current_end = farthest
                if current_end >= len(nums)-1:
                    break
        return jumps

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