LeetCode 3无重复字符的最长子串给定解法的时间复杂度求解

结论 #

你提供的解法最坏时间复杂度为O(n²)，算法时间复杂度通常以最坏情况作为标准，因此该解法的时间复杂度判定为O(n²)。

推导过程 #

• 最坏场景验证：当输入字符串的所有字符均不重复时（例如s = "abcdefghij"），每一轮左指针l向右移动一位后，右指针r都会从l的位置一直遍历到字符串末尾才会触发边界判断。总遍历次数为等差数列求和：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2，显然属于平方级复杂度。
• 最好场景补充：如果输入字符串所有字符完全重复（例如s = "aaaaaaaa"），每一轮左指针移动后，右指针仅走1步就会触发重复判断，总遍历次数为2n，属于O(n)复杂度，但该场景属于极端个例，不代表算法的通用性能。
• 性能损耗根因：该写法每次遇到重复字符时都会将右指针重置为左指针的当前位置，导致已经遍历过的字符被重复访问，而优化版的滑动窗口解法不会回退右指针，因此可以做到稳定O(n)的时间复杂度。

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