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

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

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

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

d18

2018-09-21 16:15:47 +08:00

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

LadyChunsKite

2018-09-21 16:28:28 +08:00

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

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 吧。

sagaxu

2018-09-21 16:50:26 +08:00 via Android

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

menc

2018-09-21 17:01:58 +08:00

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

menc

2018-09-21 17:04:06 +08:00

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

liprais

2018-09-21 17:11:54 +08:00

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

stevenbipt

2018-09-21 17:15:43 +08:00 via Android

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

LadyChunsKite

2018-09-21 17:17:21 +08:00

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

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

lance6716

2018-09-21 17:17:34 +08:00 via Android

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

sagaxu

2018-09-21 17:21:22 +08:00 via Android

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

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

ylsc633

2018-09-21 17:23:27 +08:00

没用 python 解过

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

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

lance6716

2018-09-21 17:33:03 +08:00

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

ddzzhen

2018-09-21 18:55:12 +08:00 via Android

@Raisu 高手

ddzzhen

2018-09-21 18:56:16 +08:00 via Android

@d18 哎，才疏学浅

ddzzhen

2018-09-21 18:58:41 +08:00 via Android

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

loryyang

2018-09-21 19:17:27 +08:00

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

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

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

Raisu

2018-09-21 19:36:15 +08:00

我也是新手啊。。。自学转开发才半年，

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

ddzzhen

2018-09-21 23:05:43 +08:00

@loryyang 多谢高手,确实学了 python 感觉效率是个瓶颈

ddzzhen

2018-09-21 23:06:15 +08:00

@Raisu 多谢,当时解题的时候考虑过这个,但是没有实施