问题是leetcode上的一道算法题。https://oj.leetcode.com/problems/two-sum/
我用的是python来写的,但是总是提示Time Limit Exceeded 错误,当出现一个大数组的时候。这是我的解决方案。
def twoSum(num, target): for i in range(0, len(num)): num1 = num[i] num2 = target - num1 if num2 in num and (i+1) !=num.index(num2) + 1: return (i+1,num.index(num2) + 1)
不知道为什么是报错。这是我再网上看的别人的方法。
def twoSum(self, num, target): processed = {} for i in range(0, len(num)): if target-num[i] in processed: return [processed[target-num[i]]+1,i+1] processed[num[i]]=i
我并不觉得好,因为它把数据又放到了dict中,每次再去读dict里面是否有这个num,但是为什么它的算法就比我的快呢?求解释。提前谢过。
你可知
num2 in num
和target-num[i] in processed
的时间复杂度分别是多少?从字典查找一个元素比从list中查找要快吧。 字典不是类似hash表查找方式么