为什么创建一个集合并在每个循环中获取其 len 比预先完成要花费更长的时间？

Question

m = len(set(nums))
n = len(nums)
ans = 0
for i in range(n):
    s = set()
for j in range(i, n):
    s.add(nums[j])
    ans += len(s) == m
return ans

从上面的代码中，当我将

m

替换为

len(set(nums))

并与

len(s)

进行比较时，则超出了时间限制，其中

1 <= nums.length <= 1000

。 有人能解释一下为什么吗？

n = len(nums)
ans = 0
for i in range(n):
    s = set()
for j in range(i, n):
    s.add(nums[j])
    if len(s) == len(set(nums)):
        ans += 1
return ans

Answer 1

在上面的代码中，

m = len(set(nums))

，您正在预先计算

m

的值。要计算

m

，需要 O(n) 作为时间复杂度，其中 n = no。

nums

中的元素。在上面的代码中，

m

的值是常数。

但是在下面的代码中，您在 for 循环中将

m

替换为

len(set(nums))

。因此，对于 for 循环的每次迭代，都会计算

m

的值。每次迭代的时间复杂度为 O(n)。因此，总的来说，计算 m 的时间复杂度为

O(n^2)

。

这就是为什么它显示超出时间限制