LeetCode55跳跃游戏：为何当前for循环比注释版执行更快？

问题背景 #

在解决LeetCode第55题「跳跃游戏」时，两段看似迭代次数相同的for循环代码，性能表现天差地别：注释掉的旧循环仅通过75个测试用例就超时，替换后的新循环则超过70%的Python提交速度。

代码对比 #

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        i = 0
        n = len(nums)
        next = None
        
        if(n==1):
            return True
        
        while(i < n):
            ni = nums[i]
            
            if(ni==0):
                return False
            
            if(i==(n-1)):
                break           
            
            max = 0

            # 超时的旧循环
            # for j in range(ni):
            #     imb = i+j+1+nums[i+j+1]
            #     if(max<imb):
            #         max = imb
            #         next = i+j+1
            #
            #     if(max >= (n-1)):
            #         return True

            # 性能更优的新循环
            for j in range(i, i+nums[i]+1):
                if j+(nums[j]) >= max: 
                    max = j+(nums[j])
                    next = j

                if(max >= (n-1)):
                    return True

            i = next
        
        return False

性能差异原因 #

• 索引计算的冗余开销：旧循环中每次都要通过i+j+1转换为数组实际索引，还要重复执行i+j+1 + nums[i+j+1]的加法运算；新循环直接用j作为当前遍历的索引，j + nums[j]的计算更直接，减少了不必要的运算步骤，CPU执行的指令数更少。
• 循环范围的优化处理：旧循环的range(ni)生成的是0到ni-1的序列，每次都要手动转换为数组索引；新循环的range(i, i+nums[i]+1)直接生成目标索引范围，Python对连续整数范围的遍历有内部优化，执行效率更高。
• 缓存局部性的影响：新循环是连续遍历数组中从i开始的一段元素，数组在内存中是连续存储的，CPU缓存可以高效预加载这段数据，减少缓存未命中的概率；旧循环虽然也是访问连续的数组位置，但每次都要计算索引，相比直接遍历，缓存利用效率更低，在大数组测试用例中这种差异会被放大。
• 提前返回的触发效率：两段代码都有提前返回逻辑，但新循环的j + nums[j]计算更直接，在某些测试用例中可能更早触发max >= n-1的条件，提前结束循环，减少不必要的迭代。

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