算法学习-求两数之和
解题思路:
题目本身难度不大,难度大的地方在于时间限制和python知识
最开始想到的方法就是双层循环,求和判断.但是这个方法在最后一个例子测试的时候超时了(我本地i7需要10秒时间)
然后查了一下list的方法,发现有一个index函数,可以求值在队列中的序号
那么可以先排序,再处理.因为是排过序了,所以只要和大于target了,就可以终止循环,进一步提高时间了
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List
:type target: int
:rtype: List
"""
cacls = nums[:]
cacls.sort()
for i in range(len(cacls) - 1):
for j in range(i + 1, len(cacls)):
if cacls + cacls == target:
head = nums.index(cacls)
tail = nums.index(cacls)
if head == tail:
tail = nums.index(cacls, head + 1)
ret =
ret.sort()
return ret
if cacls + cacls > target:
break
return []
这个题目还有一个更好的方法,就是利用dict,这个算法如下,理论上消耗的时间是O(n)
def twoSum(nums, target):
data = dict()
for i in range(len(nums)):
if nums not in data:
data] = i
else:
return ], i]
return [] 应用数学思想 好像做过，leetcode还是lintcode的题:eee 估计是想让你用lambda表达式吧，你试试能不能做出来，我才学有限，只是提供下思路哈 为什么我写的两层循环没有超时 qichen 发表于 2018-11-21 10:56
好像做过，leetcode还是lintcode的题
这个是LeetCode的题目,我打算从第一题往后尽可能的做,欢迎随时讨论 Bayminx 发表于 2018-11-21 11:38
估计是想让你用lambda表达式吧，你试试能不能做出来，我才学有限，只是提供下思路哈
lambda表达式可以用来生成,但是这里面情况有点复杂,原始数据是没有排序的,而且存在相同值的元素
单纯用lambda很难完美通过所有例子 KID丶 发表于 2018-11-21 13:45
为什么我写的两层循环没有超时
你要不发上来我也学习一下,看看我的问题在哪里?
我这个是LeetCode题库第1题 zerglurker 发表于 2018-11-21 21:45
你要不发上来我也学习一下,看看我的问题在哪里?
我这个是LeetCode题库第1题
明天给你发一下，
页:
[1]
2