字典中“in”运算符的时间复杂度

Question

在Leetcode中解决二和问题时我使用了这个解决方案

    hashm = {}
    for i,n in enumerate(nums):
        new_target = target - n
        if new_target in hashm:
            return [hashm[new_target], i]
        else:
            hashm[n] = i

第 4 行是否使其成为 O(n^2)？

然后我使用了这个解决方案

    hashm = {}
    ss = set()
    for i in range(len(nums)):
        val = target - nums[i]
        if val in ss:
            return[i,hashm[val]]
            break
        else:
            hashm[nums[i]] = i
            ss.add(nums[i])

Answer 1

您对第一个解决方案的时间复杂度的担忧是可以理解的，但需要注意的是它实际上是 O(n)，而不是 O(n^2)。让我们来分析一下这是为什么。

第一个解决方案分析

hashm = {}
for i, n in enumerate(nums):
    new_target = target - n
    if new_target in hashm:
        return [hashm[new_target], i]
    else:
        hashm[n] = i

• 哈希表（字典）操作：这里的关键操作是字典查找（如果 hashm 中有 new_target）和插入（hashm[n] = i）。在 Python 中，这些操作通常为 O(1)，这意味着无论字典大小如何，它们都需要恒定的时间。

• 单次遍历 nums：对于 nums 中的每个元素，循环运行一次。这使其成为线性迭代，从而导致 O(n) 复杂度。

• 总体复杂度：由于每次迭代执行恒定时间操作（字典查找/插入），因此循环的总体复杂度为 O(n)。

第二解分析

hashm = {}
ss = set()
for i in range(len(nums)):
    val = target - nums[i]
    if val in ss:
        return [i, hashm[val]]
        break
    else:
        hashm[nums[i]] = i
        ss.add(nums[i])

• 哈希表和集合操作：与第一种方案类似，字典和集合操作一般都是O(1)。

• 附加集：您在这里使用附加集（ss），但这不会改变复杂性。字典和集合都用于恒定时间的查找和插入。

• 总体复杂度：循环仍然对 nums 中的每个元素迭代一次，每次迭代的操作都是 O(1)，所以这种方法也是 O(n)。

比较

• 两种解决方案都有效地使用哈希表在恒定时间内存储和查找值。

• 第二种方案使用了额外的集合，但这并没有改变整体的时间复杂度；仍然是 O(n)。该集合似乎有点多余，因为字典 hashm 已经用于跟踪元素及其索引。

• 就空间复杂度而言，两个解决方案都是 O(n)，因为它们将列表中的元素存储在哈希表中（并且在第二个解决方案中也是一个集合）。

您的两个解决方案的时间复杂度都是 O(n)。使用哈希表（Python 中的字典）可以实现高效的恒定时间查找，从而避免需要嵌套循环，这将是 O(n^2) 解决方案的特征。