python - 哪个在 Python : list. index() 或 dict.get() 中更有效

Question

我正在尝试解决 a problem on LeetCode.我正在使用 Python，我做了如下尝试:

def twoSum(self, num, target):
    index0 = 0
    index1 = -1 
    for item in num:
        index0 += 1
        other = target - item
        try:
            index1 = num[index0:].index(other)
            index1 += index0 + 1
        except ValueError:
            continue
        else:
            break
    return index0, index1

但我总是得到结果:Time Limit Exceeded
我的代码的想法是检查列表中是否有 element(other = target - item)，为此我使用了 index() 方法。

网上给出的正确答案如下:

def twoSum(self, num, target):
    length = len(num)
    dic = {}
    for i in xrange(length):
        dic[num[i]] = i
    index0 = -1
    index1 = -1 
    for key in xrange(length):  #not "for key in dic.values():" 
        other = target - num[key]
        index1 = dic.get(other)
        #[1, 2, 3, 4], 4:   2,2 is not the EXPECTED answer.
        if index1 and index1 != key:
            index0 = key + 1
            index1 += 1
            break

    return index0, index1

没问题，但我不明白我的代码有什么问题？ list.index() 是否比 dict.get() 慢？

Answer 1

Is list.index() slower than dict.get()?

简而言之，是的:list.index() 必须扫描列表以查找元素，而 dict.get() 可以在constant time (即时间独立于字典的大小)。

因此第一个算法的 time complexity是输入大小的二次方(写为 O(n^2))，而第二个算法是线性的 (O(n))。

下图说明了两种增长率之间的差异: