二和问题的时间复杂度是多少？

Question

我正在练习我的大O符号，需要一些清晰度。 这是我对Leet码二和问题的解答。基本上，给定一个列表和一个目标值，返回两个加在一起的索引。 比如说

twoSum([1,2,3,4],7)

将返回[2,3]

我可以在leetcode上看到解决方案，但我想检查我对这段代码的评估是否正确。时间复杂度=O（n平方），因为外部循环中的阵列正在运行。 这是正确的吗

代码是

def twoSum_n2(nums, target):
    for idx, value in enumerate(nums): #O(n)
        diff = target - value # O(1)
        try:
            diff_idx = nums.index(diff) #O(n)
        except ValueError as ex:
            continue
        if idx != diff_idx: # O(1)
            return [idx, diff_idx] #O(1)
    return [] 

Answer 1

diff_idx = nums.index(diff) #O(n)

上面的行将运行n次，因为它位于nums列表上的for循环中。因此，将执行检查的总次数为O（n^2）次，这将复杂性提高到O（n^2）

Answer 2

是的，在当前的实现中它是O（n^2），因为一个O（n）在另一个O（n）中。当我们遇到类似的情况时，我们需要乘以这些O-s的值