LeetCode | 两数之和

努力在北京混出人样

发布于 2018-05-14 14:41:58

6660

发布于 2018-05-14 14:41:58

文章被收录于专栏：祥子的故事

基础不好，笔试代码题没做好，校招没offer，赶紧来刷题

- 两数之和

两数之和

这里采用两种方法来做，比较性能。

列表

nums = [i for i in  range(1,100000000)]
target = 3
class Solution(object):
    def twoSum(self,nums,target):
        if len(nums) <= 1:
            return False
        L = []
        for i in range(len(nums)):
            if nums[i] in L:
                return [num[i],i]
            else:
                L.append(target - num[i])

字典

class Solution(object):
    def twoSum(self,nums,target):
        if len(nums) <= 1:
            return False
        L = {}
        for i in range(len(nums)):
            if nums[i] in L:
                return [num[i],i]
            else:
                L[target - num[i]] = i

从代码来看，差别就在L 是列表还是字典类型。那我们来比较下他们的计算时间吧

比较计算时间

from time import time
nums = [i for i in  range(1,100000000)]
t = time()

target = 3
class Solution(object):
    def twoSum(self,nums,target):
        if len(nums) <= 1:
            return False
        L = []
        for i in range(len(nums)):
            if nums[i] in L:
                return [num[i],i]
            else:
                L.append(target - num[i])

print time()-t           


t = time()       
target = 3
class Solution(object):
    def twoSum(self,nums,target):
        if len(nums) <= 1:
            return False
        L = {}
        for i in range(len(nums)):
            if nums[i] in L:
                return [num[i],i]
            else:
                L[target - num[i]] = i

print time()-t

结果：