LeetCode第3题超时求助：如何优化最长无重复子串暴力解法？

原暴力解法的问题 #

你的暴力解法时间复杂度是O(n³)：

• 两层循环枚举所有子串，时间复杂度为O(n²)
• 每次检查子串是否有重复时，count_characters里的s.count(i)会遍历整个子串，单此操作就是O(k)（k为子串长度），叠加后整体复杂度直接升到O(n³)，面对长输入必然超时。

最优解法：滑动窗口+哈希表 #

用滑动窗口维护一个无重复字符的区间，搭配哈希表记录每个字符最后出现的位置，能把时间复杂度降到O(n)，完全可以通过长输入测试。

思路

1. 用left和right两个指针表示当前窗口的左右边界，初始都为0
2. 用哈希表last_pos存储每个字符最近一次出现的索引
3. 遍历right指针，逐个处理每个字符：
   • 如果当前字符已经在last_pos中，且它的最后出现位置 >= left（说明在当前窗口内重复了），就把left移动到该字符上次出现位置的下一位，保证窗口内无重复
   • 更新当前字符的最后出现位置为right
   • 计算当前窗口长度（right - left + 1），更新最大长度max_len

优化后的Python代码

def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    last_pos = {}  # 存储字符到最后出现索引的映射
    max_len = 0
    left = 0
    
    for right, char in enumerate(s):
        # 如果字符已存在且在当前窗口内，移动左指针
        if char in last_pos and last_pos[char] >= left:
            left = last_pos[char] + 1
        # 更新字符的最后出现位置
        last_pos[char] = right
        # 计算当前窗口长度并更新最大值
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
    
    return max_len

为什么这个解法更快？ #

每个字符只会被right指针遍历一次，left指针只会向右移动不会回溯，整体最多遍历2n次（左右指针各n次），时间复杂度是O(n)，空间复杂度是O(min(m, n))——m是字符集的大小（比如ASCII字符集是128，空间为固定O(1)）。

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