为何仅含单个for循环的代码时间复杂度为O(N²)？

为什么你的代码是O(N²)复杂度？ #

核心问题出在循环内的数组全量比较操作：
你在每次循环里都执行了count == [0] + [1] * (X)，这个操作需要逐元素对比两个长度为X+1的数组，时间复杂度是O(X)。当X的规模接近N时（比如X=N，数组刚好是1到N的序列），每次循环的O(X)就等价于O(N)，外层再套O(N)的循环，整体时间复杂度直接变成O(N×N)=O(N²)，这就是性能测试不通过的原因。

优化后的O(N)复杂度方案 #

用一个计数器跟踪已收集到的1~X的数字数量，替代全数组比较，每次循环只做O(1)的操作：

def Solution(X, A):
    count = [0] * (X + 1)
    collected = 0
    for i in range(len(A)):
        num = A[i]
        # 只处理1~X范围内的数字，避免无效操作和数组越界
        if 1 <= num <= X and count[num] == 0:
            count[num] = 1
            collected += 1
            # 收集齐所有数字时直接返回当前索引
            if collected == X:
                return i
    # 循环结束仍未收集齐所有数字，返回-1
    return -1

优化说明 #

• 用collected变量替代全数组比较，每次更新和判断都是O(1)操作，彻底把时间复杂度降到O(N)
• 增加了数字范围判断，避免处理大于X的无效值，同时防止数组索引越界
• 去掉了冗余的单元素分支逻辑，通用代码已经覆盖所有边界情况（比如X=1、A=[1]或A=[2]的场景）

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