使用列表时Python中“in”关键字的时间复杂度？ Leetcode

Question

我到处读到“in”运算符的时间复杂度为 O(n)，但我在代码中使用了它并且不知道为什么，但它的表现就好像它的时间复杂度为 O(1)

所以我在 leetcode 上解决了一个问题，最终得到了这个算法

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        i=0
        n=len(nums)
        for i in range (0, n-1):
            if (target-nums[i]) in nums:
                for j in range (i+1, n):
                    if nums[i]+nums[j]==target:
                        return[i, j]

我最终得到的运行时与涉及哈希图的代码非常相似：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hash_map = {}

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hash_map.keys():
                return [i, hash_map[complement]]
            hash_map[nums[i]] = i

这很奇怪，因为我到处都读到列表的 in 运算符的时间复杂度是 O(n)，所以我假设这一行

if (target-nums[i]) in nums:

将使我的代码等同于

class Solution(object):
    def twoSum(self, nums, target):
        self=list()
        n=len(nums)
        for i in range(n-1):
          for j in range(i+1,n):
            if nums[i]+nums[j]==target:
              return [i,j]

但是它具有使用哈希图的代码的运行时，并使用使用相同列表的代码的内存，因此 O(1)，有人可以向我解释一下吗？ 回顾一下，解决方案 1 的运行时间不应该与解决方案 3 更接近或完全相同吗？但它更接近解决方案2。

No1 No2和No3有每个代码的运行时和内存的截图。

Answer 1

您选择使用 Python 2，因此

if complement in hash_map.keys():

创建一个键列表并在该列表中进行搜索。而不是在哈希映射中进行快速查找。完全否定了它最初使用的原因。删除

.keys()

。或者选择 Python 3，无论如何你都应该选择它。 Python 2 已死。