为什么嵌套循环的时间复杂度是O(n)

Question

我在做Leetcode问题“没有重复字符的最长子串”并遇到了这个解决方案。

# use a set to keep track of letters and their index
    window = set()
    res = 0
    l = 0
    for r in range(len(s)):
        # remove letter until there is a dupe
        while s[r] in window:
            window.remove(s[l])
            l += 1

        # either its a new char or we got rid of dupe
        window.add(s[r])
        res = max(res, r-l+1)
            
    return res

视频说这是一个 O(n) 时间复杂度的程序，但我很困惑这是怎么回事。 for循环内有一个条件while循环，所以不会是O(n^2)。我对 Big O 还很陌生，所以我很困惑如何计算不同情况下嵌套循环的时间复杂度。

Answer 1

这是标准的滑动窗口解决方案。请注意，每个字符都会添加到窗口一次，并且最多可以从窗口中删除一次。因此，内部 while 循环的迭代总数不会超过 N（字符串中的字符数）。