LeetCode两数之和(Two-Sum)生成器实现超时问题咨询

核心结论 #

第二版超时本质是O(n²)暴力解法本身处于超时边缘，叠加生成器封装引入的额外运行开销，最终突破时间限制，和生成器本身的特性无关，属于实现方式和场景不匹配导致的性能退化。

具体原因拆解 #

• 两版解法的时间复杂度完全一致，均为O(n²)的暴力遍历
  两版代码都是通过双重循环枚举所有不重复的两数组合，没有做任何算法层面的优化。在超时测试用例中，nums长度为10000，需要枚举的组合总数为10000*9999/2 ≈ 5000万次，纯Python环境下执行5000万次简单判断本身就需要2~3秒，已经接近LeetCode对Python题解的时间阈值，任何额外开销都可能导致超时。
• 生成器封装引入了多段可观测的额外开销，在千万级循环下被大幅放大
  相比第一版直接在单函数内写嵌套循环，第二版的生成器写法新增了三类不必要的性能损耗：
  1. 每次yield [i,j]都会创建一个新的长度为2的列表对象，5000万次循环就会产生5000万个临时列表，伴随大量的内存分配、垃圾回收操作
  2. 生成器迭代需要跨函数做上下文切换：每次从twoSum函数迭代取下一个值时，都要跳转到double_loop生成器的执行栈恢复状态、取值、再跳转回twoSum，比单函数内的循环跳转多了栈帧切换的成本
  3. 拿到生成器返回的列表后，还需要通过result[0]、result[1]做索引取值才能拿到坐标，比第一版直接使用循环变量first、second多了一层索引访问操作
• 测试用例的答案位置放大了开销影响
  超时用例的目标值为19999，对应的是数组最后两个元素（9999和10000），也就是说代码必须遍历完所有5000万种组合才能找到答案，所有额外开销都会完整累加，没有提前终止的空间。第一版8385ms的耗时本身已经超过8秒，属于测试用例波动下勉强通过的水平，第二版叠加开销后耗时直接突破时间上限，触发超时。

该实现思路的核心问题 #

• 优化方向错位：代码可读性优化不能以显著增加热路径（高频执行的核心循环）开销为代价，生成器适合处理流式数据、懒加载序列的场景，不适合放在千万次执行的内层循环里做逻辑拆分
• 没有从根源解决性能问题：两数之和的最优解法是基于哈希表的单次遍历，时间复杂度为O(n)，在10000长度的数组下运行耗时不到1毫秒，比暴力解法快4个数量级。只在循环写法、控制语句上做调整，本质是在常数项上抠性能，无法解决复杂度带来的本质性能瓶颈。

哈希表版本参考实现：

def twoSum(nums: List[int], target: int) -> List[int]:
    num_index = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_index:
            return [num_index[complement], i]
        num_index[num] = i

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