LeetCode two_sum两数之和Python题解的内存与空间复杂度是否高效？

你的解法虽然可以通过判题，但仅在内存占用上表现尚可，时间效率存在明显缺陷，远达不到最优水平，具体分析如下：

• 内存/空间复杂度表现
  不计输入数组本身的内存占用，你的代码仅额外申请了固定长度的结果列表ans，没有其他随输入规模增长的内存开销，额外空间复杂度为O(1)，这部分没有冗余浪费，内存占用是很低的。
• 时间复杂度表现（核心短板）
  你的代码整体时间复杂度为O(n²)，在大输入量下性能很差：
  • 循环内的compliment in nums成员判断，本质是从头到尾遍历整个数组匹配值，单次操作耗时O(n)
  • 后续调用nums.index(compliment)查找补数对应的下标，同样是从头遍历数组查找，单次操作耗时也是O(n)
  • 两个O(n)操作嵌套在长度为n的外层循环中，总耗时随数组长度增长呈平方级上升，当数组长度达到10^4级别时，运行耗时会非常高，很容易触发超时。
    另外这个写法还有逻辑冗余：你对同一个补数做了两次遍历查找（一次判断存在、一次找下标），而且如果数组存在重复值，index()永远返回第一个匹配的下标，会产生不必要的判断分支。

效率优化方案 #

如果追求时间效率最优，可以用哈希表（Python字典）存储已经遍历过的元素和对应下标，把时间复杂度降到O(n)：

该方案的额外空间复杂度为O(n)（最坏场景下需要存储n-1个元素到哈希表），但哈希表的成员判断、下标查找都是O(1)级别，是这道题的通用最优实现，参考代码如下：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_index = {}
        for idx, num in enumerate(nums):
            complement = target - num
            if complement in num_index:
                return [num_index[complement], idx]
            num_index[num] = idx
        return []

如果你对内存占用有极致要求，不能接受O(n)的额外空间，可以先把数组元素和原下标绑定后排序，再用双指针夹逼找结果，额外空间复杂度可以压到O(1)（不计排序的内部开销），时间复杂度为O(nlogn)，是时间和内存的折中选择。

内容的提问来源于stack exchange，提问作者Umme Habiba