算法学习-求两数之和

zerglurker

题目内容

解题思路:
题目本身难度不大,难度大的地方在于时间限制和python知识
最开始想到的方法就是双层循环,求和判断.但是这个方法在最后一个例子测试的时候超时了(我本地i7需要10秒时间)
然后查了一下list的方法,发现有一个index函数,可以求值在队列中的序号
那么可以先排序,再处理.因为是排过序了,所以只要和大于target了,就可以终止循环,进一步提高时间了

[Python] 纯文本查看 复制代码

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        cacls = nums[:]
        cacls.sort()
        for i in range(len(cacls) - 1):
            for j in range(i + 1, len(cacls)):
                if cacls[i] + cacls[j] == target:
                    head = nums.index(cacls[i])
                    tail = nums.index(cacls[j])
                    if head == tail:
                        tail = nums.index(cacls[j], head + 1)
                    ret = [head, tail]
                    ret.sort()
                    return ret
                if cacls[i] + cacls[j] > target:
                    break
        return []

zerglurker

这个题目还有一个更好的方法,就是利用dict,这个算法如下,理论上消耗的时间是O(n)

[Python] 纯文本查看 复制代码

def twoSum(nums, target):
    data = dict()
    for i in range(len(nums)):
        if nums[i] not in data:
            data[target - nums[i]] = i
        else:
            return [data[nums[i]], i]
    return []

黯夜_孤星

应用数学思想

qichen

好像做过，leetcode还是lintcode的题

Bayminx

估计是想让你用lambda表达式吧，你试试能不能做出来，我才学有限，只是提供下思路哈

KID丶

为什么我写的两层循环没有超时

zerglurker

qichen 发表于 2018-11-21 10:56
好像做过，leetcode还是lintcode的题

这个是LeetCode的题目,我打算从第一题往后尽可能的做,欢迎随时讨论

zerglurker

Bayminx 发表于 2018-11-21 11:38
估计是想让你用lambda表达式吧，你试试能不能做出来，我才学有限，只是提供下思路哈

lambda表达式可以用来生成,但是这里面情况有点复杂,原始数据是没有排序的,而且存在相同值的元素
单纯用lambda很难完美通过所有例子

zerglurker

KID丶 发表于 2018-11-21 13:45
为什么我写的两层循环没有超时

你要不发上来我也学习一下,看看我的问题在哪里?
我这个是LeetCode题库第1题

KID丶

zerglurker 发表于 2018-11-21 21:45
你要不发上来我也学习一下,看看我的问题在哪里?
我这个是LeetCode题库第1题

明天给你发一下，