塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-1两数之和

最初想法:
直接用穷举遍历两两相加,结果超时了。

改进:

method1:固定第一个数,target-第一个数得到第二个数的值,可以提高速度。

method2:建立一个hash表辅助。

原始版本:

1
2
3
4
5
6
7
8
9
10
def twoSum(nums, target):
#两两组合
mylist=[]
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] + nums[j] == target:
mylist.append(i)
mylist.append(j)
return mylist
return [0,0]

method1:还是超时

1
2
3
4
5
6
7
8
9
10
def twoSum(self, nums, target):  
mylist=[]
for i in range(len(nums)):
value = target - nums[i]
for j in range(i+1, len(nums)):
if nums[j] == value:
mylist.append(i)
mylist.append(j)
return mylist
return [0,0]

使用内置函数 in 和 nums.index()

1
2
3
4
5
6
7
8
9
def twoSum(nums, target):
mylist=[]
for i in range(len(nums)):
value = target - nums[i]
if value in nums[i+1:]:
mylist.append(i)
mylist.append(nums.index(value,i+1))#从i+1后查询,缩短时间
return mylist
return [0,0]

method2:建立辅助hash表,比之前方法速度都快

1
2
3
4
5
6
7
8
9
10
def twoSum(nums, target):
elem2id = {}
for id, elem in enumerate(nums):
elem2id[elem] = id
for id, elem in enumerate(nums):
if target - elem in elem2id:
y = elem2id.get(target -elem)
if id!=y:
return [id,y]
return [0,0]

最终版本

边建表边查询,比上一种方法速度稍有提升。

1
2
3
4
5
6
7
def twoSum(nums, target):
elem2id = {}
for id, elem in enumerate(nums):
if target - elem in elem2id:
return [elem2id.get(target-elem),id]
elem2id[elem] = id
return [0,0]
if help:小手一抖点个广告 or 大手一挥资助一下