推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
各位大佬，请教一下领扣的超出时间限制-python3-第 167 题-两数相加
ddzzhen · 2018-09-21 15:27:42 +08:00 · 7451 次点击这是一个创建于 2255 天前的主题，其中的信息可能已经有所发展或是发生改变。
小弟是个新手，只会写简单的代码实现结果，对于语法的复杂度没有太多概念，使用以下链接完成领扣第 167 题时，提交代码验证到最后一步 16/17，提示：超出时间限制，感觉可能是遍历列表太多次了，但是如何知道每一步的时间复杂度到底有多大呢？
 |
1
Raisu 2018-09-21 15:54:01 +08:00
l , r = 0, len(numbers) -1
while numbers[l] + numbers[r] != target: if numbers[l] + numbers[r] > target: r -= 1; else: l += 1 return [l+1, r+1] |
 |
2
youngitachi 2018-09-21 16:08:16 +08:00
原本最简单（但是不完全靠谱）的方法就是看有几层 for 循环，但是你调用库函数却遮盖了你对复杂度的分析。
想想看 index 函数的复杂度哈，虽然没去看源码，但是这个查找应该还是去顺序遍历的，也就是说，相当于还是要用一个 for 循环去遍历的，故实际上是两层 for 循环的复杂度，O(N^2)咯。 这题有 O(N)的解法，次一点，你在查找的时候写个二分查找，也可以到 O(N log(N))，一楼的写法就是 O(N)的，可以好好体会一下（先自己想想解法吧）。 |
 |
3
d18 2018-09-21 16:15:47 +08:00
同学，刷题就不要用 python 了，和作弊有什么区别。
像这句“ if sec_num in numbers:”，就是遍历了一遍列表，不超时就怪了。 |
 |
4
LadyChunsKite 2018-09-21 16:28:28 +08:00
@d18 刷题用 python 怎么就作弊了？算法题和语言有什么关系？
|
 |
5
menc 2018-09-21 16:42:10 +08:00
@LadyChunsKite
有关系，不好算时间复杂度。 if element in list: blabla 这句话看起来像一句话，实际上是 O(n)的时间复杂度。 python 内置 sort 好用的一比，还内置了 itertools 这些东西，实现全排列和笛卡尔积都是一句话的事。 可是你知道它们时间复杂度是多少么？ 如果题目考察的就是全排列的实现，你用 itertools 又有什么意义。 所以如果一定要用 python，建议写成 C 那样原始的形式，但是这样一定有人说“不优雅 /不 pythonic/python 内置了干嘛不用”。 那就别用 python 了，统一用 c/cpp 吧。 |
|
8
menc 2018-09-21 17:04:06 +08:00
|
 |
9
liprais 2018-09-21 17:11:54 +08:00
https://www.v2ex.com/t/382458#reply59
v2ex 有一点好处就是不能删帖 |
 |
10
stevenbipt 2018-09-21 17:15:43 +08:00 via Android
Python 太慢了，更得考虑时间复杂度问题了，C/C++和 java 速度相对快上不少，n²复杂度应该都不会出线超时，但是 Python 不好说
|
|
11
LadyChunsKite 2018-09-21 17:17:21 +08:00
@menc 我觉得这不是 python 的问题，而是写代码的人的问题。一些 easy 题确实用一些 pythonic 的代码很轻松就解决了。但是我觉得，随着问题难度的上升，不是靠几个 sort，几个 in 就能解决的。
就拿这题来说： https://leetcode.com/problems/boats-to-save-people/description/ 要用到排序，但我觉得没必要把排序算法写一遍，考察的重点不是排序。 |
 |
12
lance6716 2018-09-21 17:17:34 +08:00 via Android
@liprais 北航挺好啊，我们小破邮瑟瑟发抖
另外 Cpython 像我这种非 CS 专业的都能看懂，其实并不算很刁钻的要求… |
 |
13
sagaxu 2018-09-21 17:21:22 +08:00 via Android
@menc sort 在 python 中的复杂度，跟 cpp 的或者 java 的不应该有数量级上的差异。除非自己手动 sort，否则任何语言的 sort 库都会面临 python 一样的问题。
排列组合库，时间复杂度可以认为是结果条数乘以每条长度。主流实现都应该大差不差。 |
 |
14
ylsc633 2018-09-21 17:23:27 +08:00
没用 python 解过
很多题目限制 时间和空间复杂度, 偶尔还要原地! 你们用内置函数的 怎么计算这些啊? |
 |
19
loryyang 2018-09-21 19:17:27 +08:00
不是，这题就是故意卡你这种解法的，你这种暴力的方法肯定会被 judge 卡成 TLE 的。。
至于分析时间复杂度，这个你去学学呗，不难的 |
|
20
Raisu 2018-09-21 19:34:32 +08:00
dic = {}
for i in range(len(numbers)): if numbers[i] in dic: if target - numbers[i] == numbers[i]: return [dic[numbers[i]].pop(), i + 1] else: dic[numbers[i]] = [i + 1] for k in dic: if target - k in dic: if dic[k][0] < dic[target - k][0]: return [dic[k][0], dic[target - k][0]] else: return [dic[target - k][0], dic[k][0]] 讨论组里面用字典的解法，可以通过，原因是字典的检索速度会比较快一点。。。 |
|
21
Raisu 2018-09-21 19:36:15 +08:00
我也是新手啊。。。自学转开发才半年，
|
|
22
Raisu 2018-09-21 19:54:01 +08:00
试了一下，用 set 过滤了一下也能通过。。。。不过有点取巧就是了。代码怎么带格式？
l = len(numbers) a = target // 2 if a in numbers: index = numbers.index(a) if a in numbers[index + 1:]: return [index+1, index + 2] n = list(set(numbers)) for i in range(len(n)): ans = target - n[i] if ans in n: index2 = numbers.index(ans) index1 = numbers.index(n[i]) return sorted([index1 + 1, index2 + 1]) |
 |
25
vancoder 2018-09-22 02:14:11 +08:00
这不是 python 效率的问题，是你的解法时间复杂度的问题，建议学习一下如何分析算法时间复杂度
|
 |
26
widewing 2018-09-22 08:39:32 +08:00 via Android
没搞错吧楼上的各位，哪个语言没有个内置的 sort?莫非你们都用汇编的？
|
 |
27
cyrbuzz 2018-09-22 11:22:32 +08:00  1
代码里有 print，把 print 去掉吧...
in 这种语句尽量用 set 代替 list 吧。list 执行是 O(n) ，set 是 O (1)。 这个题应该是想让你用 O(n) 的解法来解，否则不会又出来一个标明 已排过序 的在用 未排过序 时的解法再解一次吧... |
Select Language