算法复杂度 - 求解释python 解决leetcode上一个问题的算法,和复杂度相关。
高洛峰
高洛峰 2017-04-17 14:25:39
[Python讨论组]

问题是leetcode上的一道算法题。https://oj.leetcode.com/problems/two-sum/
我用的是python来写的,但是总是提示Time Limit Exceeded 错误,当出现一个大数组的时候。这是我的解决方案。

def twoSum(num, target):
 for i in range(0, len(num)):
      num1 = num[i]
      num2 = target - num1
      if num2 in num and (i+1) !=num.index(num2) + 1:
           return (i+1,num.index(num2) + 1)

不知道为什么是报错。这是我再网上看的别人的方法。

    def twoSum(self, num, target):
    processed = {}
    for i in range(0, len(num)):
        if target-num[i] in processed:
            return [processed[target-num[i]]+1,i+1]
        processed[num[i]]=i

我并不觉得好,因为它把数据又放到了dict中,每次再去读dict里面是否有这个num,但是为什么它的算法就比我的快呢?求解释。提前谢过。

高洛峰
高洛峰

拥有18年软件开发和IT教学经验。曾任多家上市公司技术总监、架构师、项目经理、高级软件工程师等职务。 网络人气名人讲师,...

全部回复(2)
大家讲道理

你可知 num2 in numtarget-num[i] in processed 的时间复杂度分别是多少?

高洛峰

从字典查找一个元素比从list中查找要快吧。 字典不是类似hash表查找方式么

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号