吾爱破解 - 52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 2966|回复: 10
收起左侧

[Python 转载] 算法学习-求两数之和

  [复制链接]
zerglurker 发表于 2018-11-21 10:09

题目内容

题目内容

解题思路:
题目本身难度不大,难度大的地方在于时间限制和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 []

免费评分

参与人数 2吾爱币 +2 热心值 +2 收起 理由
ZhXT + 1 + 1 我很赞同!
Jerry_bean + 1 + 1 用心讨论,共获提升!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

 楼主| zerglurker 发表于 2018-11-21 10:25
这个题目还有一个更好的方法,就是利用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 []
黯夜_孤星 发表于 2018-11-21 10:50
qichen 发表于 2018-11-21 10:56
Bayminx 发表于 2018-11-21 11:38
估计是想让你用lambda表达式吧,你试试能不能做出来,我才学有限,只是提供下思路哈
KID丶 发表于 2018-11-21 13:45
为什么我写的两层循环没有超时
 楼主| zerglurker 发表于 2018-11-21 21:43
qichen 发表于 2018-11-21 10:56
好像做过,leetcode还是lintcode的题

这个是LeetCode的题目,我打算从第一题往后尽可能的做,欢迎随时讨论
 楼主| zerglurker 发表于 2018-11-21 21:44
Bayminx 发表于 2018-11-21 11:38
估计是想让你用lambda表达式吧,你试试能不能做出来,我才学有限,只是提供下思路哈

lambda表达式可以用来生成,但是这里面情况有点复杂,原始数据是没有排序的,而且存在相同值的元素
单纯用lambda很难完美通过所有例子
 楼主| zerglurker 发表于 2018-11-21 21:45
KID丶 发表于 2018-11-21 13:45
为什么我写的两层循环没有超时

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

明天给你发一下,
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则

返回列表

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-11-1 06:54

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表