各位大佬，请教一下领扣的超出时间限制-python3-第 167 题-两数相加

[ddzzhen]

小弟是个新手，只会写简单的代码实现结果，对于语法的复杂度没有太多概念，使用以下链接完成领扣第 167 题时，提交代码验证到最后一步 16/17，提示：超出时间限制，感觉可能是遍历列表太多次了，但是如何知道每一步的时间复杂度到底有多大呢？

https://leetcode-cn.com/playground/TThPBRka

[Raisu]

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]

[youngitachi]

原本最简单（但是不完全靠谱）的方法就是看有几层 for 循环，但是你调用库函数却遮盖了你对复杂度的分析。

想想看 index 函数的复杂度哈，虽然没去看源码，但是这个查找应该还是去顺序遍历的，也就是说，相当于还是要用一个 for 循环去遍历的，故实际上是两层 for 循环的复杂度，O(N^2)咯。

这题有 O(N)的解法，次一点，你在查找的时候写个二分查找，也可以到 O(N log(N))，一楼的写法就是 O(N)的，可以好好体会一下（先自己想想解法吧）。

[d18]

同学，刷题就不要用 python 了，和作弊有什么区别。
像这句“ if sec_num in numbers:”，就是遍历了一遍列表，不超时就怪了。

[LadyChunsKite]

@d18 刷题用 python 怎么就作弊了？算法题和语言有什么关系？

[menc]

@LadyChunsKite
有关系，不好算时间复杂度。
if element in list:
blabla

这句话看起来像一句话，实际上是 O(n)的时间复杂度。

python 内置 sort 好用的一比，还内置了 itertools 这些东西，实现全排列和笛卡尔积都是一句话的事。
可是你知道它们时间复杂度是多少么？
如果题目考察的就是全排列的实现，你用 itertools 又有什么意义。

所以如果一定要用 python，建议写成 C 那样原始的形式，但是这样一定有人说“不优雅 /不 pythonic/python 内置了干嘛不用”。
那就别用 python 了，统一用 c/cpp 吧。

[sagaxu]

@menc 用了 python 就不会算复杂度？那只能说明不会用 python

[menc]

@sagaxu
来说下 python sort 的时间复杂度
说下 python permutation 的时间复杂度

[menc]

@sagaxu
90%的人说不出 python sort 的实现，
大多数人说个 nlgn 也只是基于当前一般 sort 的实现方法说的。

[liprais]

https://www.v2ex.com/t/382458#reply59
v2ex 有一点好处就是不能删帖

[stevenbipt]

Python 太慢了，更得考虑时间复杂度问题了，C/C++和 java 速度相对快上不少，n²复杂度应该都不会出线超时，但是 Python 不好说

[LadyChunsKite]

@menc 我觉得这不是 python 的问题，而是写代码的人的问题。一些 easy 题确实用一些 pythonic 的代码很轻松就解决了。但是我觉得，随着问题难度的上升，不是靠几个 sort，几个 in 就能解决的。

就拿这题来说：
https://leetcode.com/problems/boats-to-save-people/description/
要用到排序，但我觉得没必要把排序算法写一遍，考察的重点不是排序。

[lance6716]

@liprais 北航挺好啊，我们小破邮瑟瑟发抖
另外 Cpython 像我这种非 CS 专业的都能看懂，其实并不算很刁钻的要求…

[sagaxu]

@menc sort 在 python 中的复杂度，跟 cpp 的或者 java 的不应该有数量级上的差异。除非自己手动 sort，否则任何语言的 sort 库都会面临 python 一样的问题。

排列组合库，时间复杂度可以认为是结果条数乘以每条长度。主流实现都应该大差不差。

[ylsc633]

没用 python 解过

很多题目限制 时间和空间复杂度, 偶尔还要原地!

你们用内置函数的 怎么计算这些啊?

[lance6716]

@sagaxu 这个回答的意思就是，你属于 90%

[ddzzhen]

@Raisu 高手

[ddzzhen]

@d18 哎，才疏学浅

[ddzzhen]

@ylsc633 高手，主要是想练习一下 python，奈何逻辑完整了之后还要看复杂度，心塞

[loryyang]

不是，这题就是故意卡你这种解法的，你这种暴力的方法肯定会被 judge 卡成 TLE 的。。
至于分析时间复杂度，这个你去学学呗，不难的

[Raisu]

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]]


讨论组里面用字典的解法，可以通过，原因是字典的检索速度会比较快一点。。。