最长K不同字符子串算法中嵌套循环的时间复杂度疑问

这句话是完全正确的，你的算法时间复杂度确实是O(N)，核心原因在于滑动窗口的双指针（left和right）各自只会遍历字符串一次，没有重复处理任何字符，具体拆解如下：

• 先明确算法逻辑：你实现的应该是滑动窗口（双指针）解法——用right指针（外层for循环）逐个遍历字符串中的每个字符，当窗口[left, right]内的不同字符数量超过K时，启动内层while循环移动left指针，缩小窗口直到符合条件。

• 分析指针移动次数：

  • right指针从字符串开头走到结尾，总共移动N次（N是字符串长度），每个字符只会被right指针访问一次。
  • left指针只会向右移动，不会回退，从开头最多走到结尾，总移动次数也不会超过N次。也就是说，内层while循环虽然嵌套在外层for里，但它的总执行次数是累计的N次以内，而不是每次外层循环都执行N次。

• 总操作次数计算：外层for的N次操作 + 内层while的最多N次操作，整体总操作次数是O(N)，而非O(N²)。O(N²)的嵌套循环是指每次外层循环都会触发完整的内层循环（比如暴力枚举所有子串的情况），但这里的内层循环是“补位”式的，每个字符只会被left指针处理一次，不会重复操作。

举个简单例子：假设字符串是"aaabbbccc"，K=2。right指针逐个遍历每个字符，当走到第4个字符（第一个'b'之后的某个位置）时，窗口内不同字符数超过2，left开始移动；之后right继续走，left只会在需要的时候右移，每个字符只会被left移出窗口一次，不会反复处理之前的'a'或'b'。

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