Python中如何解决领扣第167题“两数相加”的超时问题？
小弟是个新手，只会写简单的代码实现结果，对于语法的复杂度没有太多概念，使用以下链接完成领扣第 167 题时，提交代码验证到最后一步 16/17，提示：超出时间限制，感觉可能是遍历列表太多次了，但是如何知道每一步的时间复杂度到底有多大呢？
Python中如何解决领扣第167题“两数相加”的超时问题？
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]
你遇到的超时问题，通常是因为用了暴力解法（两层循环 O(n²) 复杂度）。这题其实考的是双指针技巧，因为数组已经是升序排列的。
直接给你能AC的代码：
def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
# 题目要求索引从1开始
return [left + 1, right + 1]
elif current_sum < target:
left += 1 # 和太小，左指针右移
else:
right -= 1 # 和太大，右指针左移
return [] # 理论上题目保证有解，这里只是防御性编程
# 测试用例
print(twoSum([2, 7, 11, 15], 9)) # 输出 [1, 2]
print(twoSum([2, 3, 4], 6)) # 输出 [1, 3]
核心思路：
- 左指针从数组头开始，右指针从数组尾开始
- 计算两数之和，如果等于目标值直接返回
- 如果和小于目标值，说明需要更大的数，左指针右移
- 如果和大于目标值，说明需要更小的数，右指针左移
这样时间复杂度是 O(n)，空间复杂度 O(1)，肯定不会超时。
一句话总结：用双指针替代暴力循环。
原本最简单（但是不完全靠谱）的方法就是看有几层 for 循环，但是你调用库函数却遮盖了你对复杂度的分析。
想想看 index 函数的复杂度哈，虽然没去看源码，但是这个查找应该还是去顺序遍历的，也就是说，相当于还是要用一个 for 循环去遍历的，故实际上是两层 for 循环的复杂度，O(N^2)咯。
这题有 O(N)的解法，次一点，你在查找的时候写个二分查找，也可以到 O(N log(N))，一楼的写法就是 O(N)的，可以好好体会一下（先自己想想解法吧）。
有关系，不好算时间复杂度。
if element in list:
blabla
这句话看起来像一句话，实际上是 O(n)的时间复杂度。
python 内置 sort 好用的一比，还内置了 itertools 这些东西，实现全排列和笛卡尔积都是一句话的事。
可是你知道它们时间复杂度是多少么？
如果题目考察的就是全排列的实现，你用 itertools 又有什么意义。
所以如果一定要用 python，建议写成 C 那样原始的形式，但是这样一定有人说“不优雅 /不 pythonic/python 内置了干嘛不用”。
那就别用 python 了，统一用 c/cpp 吧。
我觉得这不是 python 的问题，而是写代码的人的问题。一些 easy 题确实用一些 pythonic 的代码很轻松就解决了。但是我觉得，随着问题难度的上升，不是靠几个 sort，几个 in 就能解决的。
就拿这题来说：
https://leetcode.com/problems/boats-to-save-people/description/
要用到排序，但我觉得没必要把排序算法写一遍，考察的重点不是排序。
sort 在 python 中的复杂度，跟 cpp 的或者 java 的不应该有数量级上的差异。除非自己手动 sort，否则任何语言的 sort 库都会面临 python 一样的问题。
排列组合库，时间复杂度可以认为是结果条数乘以每条长度。主流实现都应该大差不差。
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]]
讨论组里面用字典的解法，可以通过，原因是字典的检索速度会比较快一点。。。
试了一下，用 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])
