为何LeetCode无重复最长子串解法的嵌套循环时间复杂度为O(n)

我在做LeetCode题目《无重复字符的最长子串》时，看到了如下滑动窗口解法：

# 使用集合记录窗口内的字符
window = set()
res = 0
l = 0
for r in range(len(s)):
    # 遇到重复字符时，移动左指针直到窗口内无重复
    while s[r] in window:
        window.remove(s[l])
        l += 1

    # 将当前字符加入窗口，更新最长子串长度
    window.add(s[r])
    res = max(res, r-l+1)
        
return res

视频里提到这个程序的时间复杂度为O(n)，但我对此感到困惑：代码在for循环内包含一个条件while循环，这不应该是O(n²)吗？我刚接触大O表示法，不清楚不同场景下嵌套循环的时间复杂度如何计算。

解答 #

大O表示法衡量的是所有元素被操作的总次数上限，不是单纯看循环嵌套层数。

看这段代码里的左右指针l和r：

• r指针从0到len(s)-1，每个字符只被遍历一次，总次数是n次。
• l指针只会向右移动，不会回退，每个字符最多被从集合window中移除一次，总次数也是n次。

也就是说，while循环里的操作整个程序运行下来总共只会执行n次，不会出现外层循环每跑一次，内层循环就跑n次的情况。比如处理字符串"abcabcbb"时，l只会在遇到重复字符时右移，但每个字符只会被l处理一次，不会反复操作。

所以整个程序所有操作的总次数是O(n) + O(n) = O(n)，而非O(n²)。

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