我的twoSum代码获LeetCode通过，但时间复杂度似为O(n²)，推理有误吗？

作为算法与数据结构新手，我在LeetCode上做首个题目「两数之和」时，题目要求提出时间复杂度小于O(n²)的算法，但我编写了如下双重循环代码，却获得了平台通过：

def twoSum(nums: List[int], target: int)->List[int]:
    for x in range(len(nums)):
        for y in range(x+1, len(nums)):
            if nums[x] + nums[y] == target:
                return [x, y]
    return [0, 0]

nums = [1,2,3,4]
target = 7
twoSum(nums, target)

我分析这段代码的最坏情况时，迭代次数接近O(n²)，请问是我的推理存在错误，还是LeetCode平台出现了问题？

解答 #

你的推理完全正确，这段代码的最坏时间复杂度确实是O(n²)：当数组中不存在满足条件的数对，或者满足条件的数对位于数组末尾时，内层循环会遍历完剩余所有元素，总迭代次数为n*(n-1)/2，属于O(n²)的时间复杂度范畴。

平台判定代码通过的原因在于：

• LeetCode的判题核心是代码能正确输出所有测试用例结果，且运行时间在限制范围内。对于小规模的测试用例，O(n²)的解法运行速度足够快，不会触发超时判定。
• 题目要求「时间复杂度小于O(n²)的算法」，本质是引导学习者掌握更高效的解题思路，而非强制校验代码的复杂度。平台不会直接检测你的代码复杂度，只会通过实际运行时间来间接约束。

如果要满足题目要求的时间复杂度，可以使用哈希表优化，将时间复杂度降到O(n)，示例代码如下：

def twoSum(nums: list[int], target: int) -> list[int]:
    num_map = {}
    for idx, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], idx]
        num_map[num] = idx
    return [0, 0]

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