询问Python两数求和算法的时间复杂度是否为O(n²)

你的判断是正确的，这个算法在最坏情况下的时间复杂度确实是O(n²)，原因如下：

• 外层的for x in array是一次完整的数组遍历，时间复杂度为O(n)。
• 关键在于循环内部的num in array操作：Python的列表是线性结构，检查元素是否存在时，会从头开始逐个比对元素，直到找到目标或遍历完整个列表，这个操作的时间复杂度是O(n)。
• 最坏场景下（比如数组中不存在符合条件的数对，或者符合条件的数对在数组末尾），外层循环会执行n次，每次都要执行一次O(n)的存在性检查，两者相乘就得到了O(n²)的时间复杂度。

优化方案 #

如果想把时间复杂度降到O(n)，可以用集合来存储已遍历过的元素，利用集合O(1)的查找效率：

def twoNumberSum(array, targetSum):
    seen = set()
    for x in array:
        num = targetSum - x
        if num in seen:
            return [x, num]
        seen.add(x)
    return []

这种方法用O(n)的空间换来了O(n)的时间复杂度，是更高效的实现方式。

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