如何优化无重复字符最长子串算法？滑动窗口方案需提速

我今天解决了LeetCode上的「寻找无重复字符的最长子串」问题，第一次接触到动态滑动窗口技术，这确实是个值得加入算法工具库的实用技巧。

我最初的实现用集合跟踪窗口内的唯一字符，通过双指针l和r维护窗口：右指针遍历字符串，遇到重复字符时，用while循环从左侧收缩窗口并移除字符。理论上时间复杂度是O(n)，但实际运行耗时达到6558ms，效率偏低，想请教大家有没有优化方向？

我的初始代码：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest = set()
        l = 0
        max_num = 0
        # "abcabcbb"
        for r in range(len(s)):
            # add the s[r] if not in arr
            while s[r] in longest:
                longest.remove(s[l])
                l += 1

            if s[r] not in longest:
                longest.add(s[r])
                max_num = max(max_num, (r-l) + 1)
                print(longest)
                print(max_num)
                continue

        return max_num

这个问题让我理解了数据结构选择和滑动窗口伸缩的逻辑，但效率问题还没解决。请问大家有没有遇到过这个问题？该怎么优化？

优化方案 #

1. 移除调试输出

你的代码里保留了print(longest)和print(max_num)，这两个IO操作会大幅增加运行时间，直接删掉就能显著提升速度。

2. 用哈希表替代集合，直接定位左指针位置

原代码遇到重复字符时，需要逐个移动左指针并移除集合元素，这会产生额外的循环操作。改用字典存储字符到最新索引的映射，可以直接将左指针跳到重复字符的下一个位置，把时间复杂度严格控制在O(n)：

优化后的代码：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        char_index = {}  # 存储字符及其最新出现的索引
        l = 0
        max_num = 0
        for r, char in enumerate(s):
            # 如果字符已存在且在当前窗口内，直接将左指针移到重复字符的下一位
            if char in char_index and char_index[char] >= l:
                l = char_index[char] + 1
            # 更新当前字符的最新索引
            char_index[char] = r
            # 计算当前窗口长度并更新最大值
            max_num = max(max_num, r - l + 1)
        return max_num

优化逻辑说明：

• 字典char_index记录每个字符最后一次出现的位置，遇到重复时不用逐个收缩窗口，直接跳到重复位置的下一位，减少了大量不必要的操作
• 去掉了冗余的if s[r] not in longest判断，逻辑更简洁
• 全程只需一次遍历，每个字符最多被访问两次（左右指针各一次），实际运行效率会远高于原实现

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