无重复字符的最长子串 图解题解

这道题真正在问什么

给一个字符串 s，找出其中最长的「连续且字符互不相同」的子串，返回它的长度。两个关键词都藏着约束：「连续」意味着答案是子串而不是子序列，不能跳着取字符；「互不相同」意味着窗口里任何字符最多出现一次。以题目示例 s = "abcabcbbdd" 来说，串中任何长度为 4 的连续段都必含重复字符，而开头的 "abc" 三个字符互不重复，所以答案是 3。

为什么暴力枚举所有子串会慢

最直觉的做法是枚举每个起点，从它出发一路向右扩，撞到重复字符就停，记录能扩多远。起点有 n 个，每个起点最坏要扫 O(n) 个字符，整体 O(n²)。慢的根源是大量重复劳动：相邻两个起点对应的子串绝大部分字符重叠，上一轮扫描获得的信息却被整个扔掉重来。

关键观察是：如果以 r 结尾的最长无重复子串左边界是 l，那么当右端推进到 r+1 时，新的左边界绝不可能比 l 更靠左——往左只会把刚才那个重复冲突重新引进来。左边界单调右移，这正是滑动窗口能成立的根基。

窗口不变量与哈希表各记什么

算法维护一个窗口 [l, r]，不变量是：窗口内字符互不相同，且它是以 r 结尾的最长无重复子串。配一张哈希表 last，记录每个字符最近一次出现的下标。右指针每读入一个字符 c，就查 last：如果 c 出现过且旧位置 last[c] 落在窗口内（即 last[c] >= l），说明窗口里已经有一个 c，此时把 l 直接跳到 last[c] + 1，一步排掉重复；然后更新 last[c] = r，并用窗口长度 r - l + 1 刷新答案。

注意 last[c] >= l 这个判断不能省：字符 c 可能很久以前出现过、但早已被挤出窗口，这种「窗口外的旧影子」不构成重复，左边界不该动。

为什么左指针跳到 last[c] + 1 而不是逐格挪

重复冲突的源头只有一个——窗口里那个旧的 c。要消除冲突，左边界至少要越过它，跳到 last[c] + 1 是恰好够用的最小步幅：再多跳会白白丢掉合法字符，少跳一格则旧 c 还留在窗口里。哈希表存了旧位置，所以不必让 l 一格一格试探，一次跳跃就完成收缩，正确性和效率同时成立。

还要小心一个方向性错误：遇到重复时绝不能把 l 重置回 0 重新数。l 一旦回退，已经排除的重复字符会被再次引入窗口，算法退化回 O(n²)，而且逻辑上也不对——以 r 结尾的最长窗口左边界本来就只会右移。

复杂度怎么算，边界在哪里

时间 O(n)：右指针扫一遍字符串，左指针只向右跳、全程累计也不超过 n 步，每个字符的哈希查询和写入都是 O(1)。空间 O(min(n, Σ))：哈希表里最多存字符集大小个键，比如纯小写字母时至多 26 个。

边界方面：空串答案是 0，把 ans 初始化为 0 即可自然覆盖；全部字符相同（如 "bbbb"）时窗口永远只有一格，答案 1；如果题目变体要求返回子串本身而不只是长度，在刷新最大长度的同时记下当时的 l 和 r，最后切片即可。

Python

def lengthOfLongestSubstring(s):
    last = {}        # 字符 -> 最近下标
    l = ans = 0
    for r, c in enumerate(s):
        if c in last and last[c] >= l:
            l = last[c] + 1   # 左指针跳过重复
        last[c] = r
        ans = max(ans, r - l + 1)
    return ans

C++

int lengthOfLongestSubstring(string s){
    vector<int> last(128, -1);
    int l = 0, ans = 0;
    for(int r = 0; r < s.size(); r++){
        char c = s[r];
        if(last[c] >= l) l = last[c] + 1;
        last[c] = r;
        ans = max(ans, r - l + 1);
    }
    return ans;
}

Java

int lengthOfLongestSubstring(String s){
    int[] last = new int[128];
    java.util.Arrays.fill(last, -1);
    int l = 0, ans = 0;
    for(int r = 0; r < s.length(); r++){
        char c = s.charAt(r);
        if(last[c] >= l) l = last[c] + 1;
        last[c] = r;
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}