为何循环内重复计算len(set(nums))比提前计算耗时得多？

先看两段代码的核心差异：

代码1（正常运行） #

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

代码2（超时） #

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

超时原因分析 #

1. 单次计算vs重复计算的时间成本

   • 代码1里，len(set(nums))只执行一次：将nums转成集合需要遍历所有元素，时间复杂度为O(n)，之后循环里直接调用提前存储的m，每次判断只是O(1)的数值比较。
   • 代码2里，内层循环的每次判断都会重新执行len(set(nums))——也就是每次都要完整遍历nums转成集合，再取长度，这一步每次都带来O(n)的时间开销。

2. 时间复杂度的量级差异

   • 代码1总时间复杂度为O(n²)：单次O(n)的集合转换，加上外层n次、内层平均n/2次的循环（总O(n²)次操作）。对于n=1000来说，总操作量约1e6级别，Python可轻松处理。
   • 代码2总时间复杂度为O(n³)：内层循环共执行约n²/2次，每次额外叠加O(n)的集合转换，总操作量达到1000³=1e9级别。Python每秒最多处理约1e7次操作，1e9次操作耗时近100秒，远超题目时间限制。

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