LeetCode两数之和问题：for与while循环解法效率差异疑问

问题背景 #

给定整数数组nums和整数target，返回两个数的下标，使它们的和等于target。假设每个输入恰好有一个解，且不能使用同一元素两次，返回顺序不限。

我的疑问 #

我写出两种暴力枚举不重复组合的解法（while循环和for循环实现），原本认为两者时间复杂度都是O(n²)，但while循环版本在大数据组下触发“超时”错误，for循环版本却能正常运行，想知道两者的差异在哪里。

while循环解法代码 #

num1 = 0
while num1 < len(nums):
    num2 = num1+1
    while num2 < len(nums):
        sum = nums[num1] + nums[num2]
        if sum == target:
            return [num1, num2]
        else:
            num2 += 1
    num1 += 1

for循环解法代码 #

for num1 in range(len(nums)):
    for num2 in range(len(nums)):
        if num2 > num1:
            if nums[num1] + nums[num2] == target:
                 return [num1, num2]

差异分析 #

虽然两者理论时间复杂度都是O(n²)，但实际运行的循环执行开销存在明显差异：

• 底层实现效率不同：Python的for循环基于C语言实现的迭代器，遍历range(len(nums))时的操作都在底层高效完成；而while循环里的num1 +=1、num2 +=1以及边界判断都是Python解释器层面的操作，每次循环的执行开销远大于for循环。
• 无效判断的代价抵消：for循环内层虽然会遍历所有下标，多了if num2 > num1的判断，但这个简单的整数比较操作开销极低，加上for循环本身的底层优化，整体执行速度反而超过了需要手动管理变量的while循环。
• 缓存优化适配性：for循环的连续迭代模式更符合Python解释器的缓存策略，下标遍历的局部性更好，缓存命中率更高；while循环的变量自增逻辑虽然逻辑等价，但底层指令序列不够紧凑，缓存效率略低。

总结来说，理论时间复杂度相同不代表实际运行效率一致，Python对for循环的底层优化远优于手动维护的while循环，大数据量下while循环的Python级操作累积开销最终触发了超时。

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