使用in关键字的两数之和解法时间复杂度是O(N)还是O(N²)？

这个说法是正确的，这段代码的实际时间复杂度确实是O(N²)，具体原因如下：

• 外层for循环遍历整个nums数组，本身的时间复杂度为O(N)，N为数组长度
• 循环内部的两个操作都是列表的线性查找逻辑，单次耗时都是O(N)：
  • value in nums：Python列表的成员查询没有索引优化，会从头到尾遍历列表匹配元素，最坏情况要查完所有元素
  • nums.index(value)：同样是从列表头部开始遍历寻找第一个匹配值的下标，最坏情况也是遍历全列表
• 两层线性逻辑叠加，整体最坏时间复杂度就是O(N × N) = O(N²)

你原本认为的O(N)时间复杂度解法，是使用哈希表（Python中的字典）存储已遍历元素和对应下标的版本：把已经遍历过的元素存在字典里，字典的成员查询和下标读取都是O(1)时间，这样整体只需要遍历一次数组就能得到结果，时间复杂度才是O(N)。

另外补充两个代码的小问题：

1. 代码中判断条件里的I是大写，而前面循环定义的下标变量是小写i，直接运行会报变量未定义的错误
2. return语句之后的break永远不会执行，属于冗余代码

# 附正确的O(N)时间复杂度写法参考
class Solution:
    def twoSum(self, nums, target):
        seen = dict()
        for i, v in enumerate(nums):
            value = target - v
            if value in seen:
                return (seen[value], i)
            seen[v] = i

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