请求优化两数之和算法至时间复杂度低于O(n²)

你的原算法采用两层嵌套循环，时间复杂度为O(n²)，当数组规模较大时运行效率会显著下降。可以通过**哈希表（字典）**实现空间换时间，将整体时间复杂度降至O(n)。

优化后的代码 #

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

逻辑说明 #

• 用字典num_map存储已遍历元素的数值-下标映射，实现O(1)时间的查找
• 遍历数组时同步获取当前元素的下标和值，计算需要匹配的补数（target - 当前值）
• 若补数已在字典中，直接返回补数的下标与当前下标；若不在，就把当前元素和下标存入字典继续遍历
• 题目保证输入必有唯一解，因此遍历过程中一定会找到符合条件的结果

该方案仅需遍历数组一次，字典的查找、插入操作均为O(1)，整体时间复杂度为O(n)，空间复杂度为O(n)（最坏情况需存储整个数组元素）。

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