玩了一下leetcode,做最简单的two sum问题(https://leetcode.com/problems/two-sum/ )。
首先上来用了简单粗暴的for循环,还用了两次。虽然正确算出结果,却用了6400ms的时间(大部分答案的运算时间在几十毫秒)。
# first try
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i]+nums[j] == target:
result = [i,j]
break
return result
后来尝试用library,先把list整个转化成library,再做一些算法运算。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dictA = {k: v for v, k in enumerate(nums)}
for i, el in enumerate(nums):
dictA.pop(nums[i])
if target-nums[i] in dictA.keys():
result=[i,dictA[target-nums[i]]]
else:
print(dictA)
return result
这种算法在input列表里有重复元素是会出现Runtime Error,应该array是整体转化成dict之后,有重复元素,在for loop里pop或del后便会报错。
后来朋友提醒我,何必一开始就全部转化呢?如果前两个元素就符合要求的话,全部转化之后再计算会耗费更多的资源。
于是有了后来这个算法,运算时间32ms:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dictA = {}
for i in range(len(nums)):
if target-nums[i] in dictA.keys():
result=[dictA[target-nums[i]],i]
return result
break
else:
dictA.update({nums[i]:i})
网友评论