最长K个不同字符子串代码中循环内集合转换的时间复杂度求解

你的代码整体时间复杂度是O(n²)，不会达到O(n³)。

复杂度推导过程 #

• 首先滑动窗口的两层循环总迭代次数为O(n)：window_end指针会遍历整个字符串共n次，window_start指针最多只会从左到右移动n次，不会回溯，因此for循环和嵌套的while循环加起来的总迭代次数是线性的O(n)。
• 每次迭代中的耗时操作为set(window_sum)：将当前窗口的列表转为集合的时间复杂度和当前窗口的长度成正比，为O(m)，其中m是当前窗口的字符数。
• 最坏情况总耗时：当k大于等于字符串长度时，窗口会一直扩展到整个字符串，每次set操作的长度依次是1、2、3……n，所有set操作的总耗时为1+2+...+n = n(n+1)/2 = O(n²)。
• 不会达到O(n³)的原因：无论触发多少次set操作，所有set操作处理的字符总数不会超过n²量级，不存在三重嵌套的线性操作，因此不可能达到O(n³)。

优化方案 #

你可以用哈希表（字典）统计当前窗口内各字符的出现次数，不需要每次遍历整个窗口统计不同字符数，即可将时间复杂度降到O(n)，参考实现如下：

def longest_substring_with_k_distinct(str1, k):
    result = 0
    window_start = 0
    char_count = {}
    for window_end in range(len(str1)):
        right_char = str1[window_end]
        char_count[right_char] = char_count.get(right_char, 0) + 1
        # 取字典长度即可直接得到不同字符数，O(1)操作
        while len(char_count) > k:
            left_char = str1[window_start]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            window_start += 1
        result = max(result, window_end - window_start + 1)
    return result

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