无重复字符的最长子串怎么用滑动窗口解？

简化版

求最长的、不含重复字符的连续子串。用滑动窗口 + 哈希:right 向右扩展窗口,把字符加入窗口;一旦出现重复字符,就收缩 left(移出左边字符)直到窗口内无重复;每次窗口合法时更新最大长度。因为 left、right 都只右移、各走一遍,时间 O(n)。这是「求最长」滑动窗口的典型题。

详细版

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> count = new HashMap<>(); // 窗口内字符计数
    int left = 0, max = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        count.merge(c, 1, Integer::sum);             // 加入窗口
        while (count.get(c) > 1) {                    // c 重复了 → 收缩
            char d = s.charAt(left);
            count.merge(d, -1, Integer::sum);         // 移出左字符
            left++;
        }
        max = Math.max(max, right - left + 1);        // 窗口合法，更新最长
    }
    return max;
}

窗口状态:哈希表记录窗口内每个字符的出现次数。
收缩条件:count.get(c) > 1——刚加入的 c 出现了 2 次(重复),就收缩 left 直到 c 只剩 1 个。
求最长:窗口合法时(while 后)更新 max。O(n)。

完整版教学

一、为什么是「求最长」滑动窗口

题目要「最长的无重复子串」,是典型的求最长滑窗:我们希望窗口尽量大,但必须保持窗口内无重复字符这个「合法性」。所以策略是:right 尽力扩张,一旦破坏了合法性(出现重复),就收缩 left 恢复合法,并在合法时记录最大长度。对照滑动窗口模板,它属于「不合法才收缩、合法时更新 max」这一类。

二、窗口状态:用哈希记录字符计数

窗口需要知道「里面有没有重复字符」。用一个哈希表(或 128 长度的数组) 记录窗口内每个字符出现的次数:

right 扩张,加入 s[right] 时,该字符计数 +1。
如果加入后某字符计数 > 1,说明窗口里有了重复。
收缩 left 时,移出 s[left],该字符计数 -1。

判断「窗口是否合法」就是看「有没有字符计数 > 1」——实际上只需看刚加入的那个字符 c 是否 > 1(因为重复只可能由新加入的 c 造成)。

三、收缩逻辑:直到刚加入的字符不再重复

关键细节:right 加入 c 后,如果 count[c] > 1,说明窗口里之前就有一个 c。要恢复合法,只需收缩 left 直到把那个旧的 c 移出去(此时 count[c] 回到 1)。所以 while (count.get(c) > 1) 这个条件精准地收缩到「c 不再重复」为止,不多不少。收缩过程中移出的其它字符计数也相应减 1。

四、走一个例子

s = "abcabcbb"
right=0 'a': 窗口 "a"，max=1
right=1 'b': "ab"，max=2
right=2 'c': "abc"，max=3
right=3 'a': "abca"，a 重复！收缩 left 到移出旧 a → "bca"，max=3
right=4 'b': "bcab"，b 重复！收缩 → "cab"，max=3
right=5 'c': "cabc"，c 重复！收缩 → "abc"，max=3
right=6 'b': "abcb"，b 重复！收缩 → "cb"
right=7 'b': "cbb"，b 重复！收缩 → "b"
结果 max = 3（"abc"）

五、优化:记录字符上次出现位置直接跳转

上面每次重复要一步步收缩 left。可以优化成哈希表记录每个字符「上次出现的下标」,遇到重复时让 left 直接跳到「重复字符上次位置 + 1」(取 max(left, 上次位置+1) 防止回退):

Map<Character, Integer> last = new HashMap<>();
int left = 0, max = 0;
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    if (last.containsKey(c)) left = Math.max(left, last.get(c) + 1); // 直接跳
    last.put(c, right);
    max = Math.max(max, right - left + 1);
}

这样 left 一步到位,不用循环收缩,常数更小(仍是 O(n))。注意 max(left, ...) 防止 left 往回跳。

六、复杂度与要点

时间 O(n):left、right 各遍历一次。
空间 O(k):k 是字符集大小(ASCII 最多 128)。
要点:求最长 → 不合法(有重复)才收缩、合法时更新 max;收缩条件盯住「刚加入的字符计数 > 1」;优化版用「上次位置 + 1」让 left 直接跳(记得 max 防回退)。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：窗口 [left,right] 始终无重复，left 只向右移动。

对应的状态推进是：右端加入字符后若重复就收缩，或用上次位置把 left 跳到 max(left,last+1)。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。每个字符至多进出窗口一次，O(n)。

带数字走一遍：abba 扫到第二个 b 时 left 跳到 2，后遇 a 不能把 left 退回 1。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	按字符还是 Unicode 码点计数要与题意一致
时间复杂度	O(n)
额外空间	O(字符集大小)
关键边界	跳转必须取 max，避免 left 后退；更新答案的时机要在窗口合法后
替代方案	字符集很小可用数组替代哈希表

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“按字符还是 Unicode 码点计数要与题意一致”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“每个字符至多进出窗口一次，O(n)”。
误区：重复值和边界值不会改变代码。 跳转必须取 max，避免 left 后退；更新答案的时机要在窗口合法后。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“窗口 [left,right] 始终无重复，left 只向右移动”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“abba 扫到第二个 b 时 left 跳到 2，后遇 a 不能把 left 退回 1”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“字符集很小可用数组替代哈希表”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

无重复最长子串 = 求最长滑动窗口:right 扩张加入字符(哈希计数),刚加入的字符计数 > 1(重复)就收缩 left 直到不重复,窗口合法时更新 max(right-left+1)。O(n)、空间 O(字符集)。优化:哈希记「字符上次出现下标」,重复时 left = max(left, 上次+1) 直接跳(max 防回退)。这是「不合法才缩、合法更新最长」的模板题。

简化版

详细版