LeetCode LCR 016. 无重复字符的最长子串 | 走在修行的大街上

走在修行的大街上

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

目录

题目描述

✅ LCR 016. 无重复字符的最长子串

题意分析

给定字符串 s，求其中不含重复字符的最长连续子串的长度，返回长度而不是子串本身。

两个关键词决定了算法形态。“连续”说明答案对应原串上的一段区间 [left, right]，可以用两个下标刻画；“无重复”则是一个对区间单调的性质：若 [left, right] 内无重复，它的任意子区间也无重复；反过来，一旦区间内出现重复，继续向右扩张永远不可能重新合法，只能先收缩左边界。这正是可变长滑动窗口成立的条件。

于是问题可以改写成：对每个右端点 right，求出使 [left, right] 无重复的最小 left，答案就是所有 right - left + 1 的最大值。这样枚举右端点一遍即可，不必枚举所有子串。

边界情况：s 为空时答案是 0；s 全部字符相同（如 "bbbbb"）时答案是 1；s 本身就无重复时答案是整串长度。

解法一：滑动窗口 + 最近出现位置

核心思路

暴力做法枚举 $O(n^2)$ 个子串再逐个判重，总代价 $O(n^3)$。优化的入手点在于：右端点右移一位时，上一轮窗口的合法性信息完全可以复用，不需要从头判重。

用哈希表 lastIndex 记录每个字符最近一次出现的下标。当 s[right] 加入窗口时，只有一种情况会破坏合法性——这个字符上次出现的位置 preIndex 仍落在窗口内，即 preIndex >= left。此时窗口里恰好只有这一对重复，把 left 一步跳到 preIndex + 1 就重新合法，而且这是能容纳 right 的最小左边界。

正确性来自一个不变量：每次更新答案前，[left, right] 内的字符互不相同。归纳地看，上一轮结束时窗口合法，本轮只新增了 s[right] 一个字符，所以只需排除它与窗口内旧字符的冲突，而 lastIndex 恰好给出了唯一可能的冲突位置。

left 只增不减：跳转的前提是 preIndex >= left，因此 preIndex + 1 > left 恒成立。这个单调性是线性复杂度的来源。

解题步骤

初始化：lastIndex 为空表，left = 0 指向窗口左端点，ans = 0。窗口用左闭右闭区间 [left, right] 表示。

枚举右端点：right 从 0 到 n - 1，取 ch = s[right]，把它看作本轮新加入窗口的字符。

判断冲突：取出 ch 的最近位置 preIndex。只有 preIndex 存在且 preIndex >= left 才说明重复发生在窗口内；若 preIndex < left，它早已被窗口甩在身后，属于过期信息，left 不能动。

修复窗口：冲突时令 left = preIndex + 1，一步跨过那个重复字符。这里不需要循环，因为合法窗口内该字符最多出现一次。

更新最近位置：lastIndex[ch] = right。这一步必须排在读取 preIndex 之后，否则会读到自己。

更新答案：此刻窗口已经合法，用 right - left + 1 取最大值。这个顺序不能颠倒。

返回 ans。

以 s = "abcabcbb" 走一遍：a 入窗得 [0,0]，ans=1；b 得 [0,1]，ans=2；c 得 [0,2]，ans=3；下标 3 的 a 的 preIndex = 0 >= left = 0，left 跳到 1，窗口 [1,3]，ans 保持 3；之后每轮都恰好跳一位，窗口长度稳定在 3；末尾两个 b 相邻，left 被推到 7，窗口收成 [7,7]。最终 ans = 3。

再看 s = "abba" 这个专门卡人的用例：处理下标 3 的 a 时 lastIndex['a'] = 0，但 left 已因为下标 2 的 b 重复被推到 2。0 < 2 是过期位置，left 必须保持 2，窗口为 [2,3]，答案 2。若漏掉 preIndex >= left 判断而把 left 回退到 1，就会错答成 3。

代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastIndex = new HashMap<>();
        int left = 0;
        int ans = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            Integer preIndex = lastIndex.get(ch);
            if (preIndex != null && preIndex >= left) {
                // left 只越过当前窗口内的重复字符，保证窗口边界单调右移。
                left = preIndex + 1;
            }
            lastIndex.put(ch, right);
            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}

func lengthOfLongestSubstring(s string) int {
    lastIndex := make(map[byte]int)
    left := 0
    ans := 0

    for right := 0; right < len(s); right++ {
        ch := s[right]
        if preIndex, ok := lastIndex[ch]; ok && preIndex >= left {
            // left 只越过当前窗口内的重复字符，保证窗口边界单调右移。
            left = preIndex + 1
        }
        lastIndex[ch] = right
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }

    return ans
}

复杂度分析

时间复杂度：$O(n)$，right 单调扫描 n 次，left 只增不减、总位移不超过 n，哈希查询与写入均摊 $O(1)$。

空间复杂度：$O(\min(n, k))$，k 为字符集大小，哈希表最多保存 k 个不同字符，也不会超过串长。

关键点总结

窗口能用双指针，依赖的是“无重复”对区间的单调性：合法区间的子区间一定合法。

哈希表存的是全局历史最近位置，而 left 决定哪些历史仍然有效，两者靠 preIndex >= left 衔接。

“先修窗口，再记答案”是所有可变窗口题的固定次序。

一步跳跃能替代逐格收缩，前提是能直接算出新的左边界。

解法二：滑动窗口 + 字符计数

核心思路

换一个视角：不记位置，而是维护窗口内每个字符的出现次数 count。

s[right] 入窗后令其计数加一，若 count[ch] > 1 说明窗口非法，就反复移出 s[left]（计数减一、left 右移），直到 count[ch] 回到 1。收缩一定会终止，最坏情况是左端点推进到与 right 重合，窗口只剩一个字符。

它比“最近位置”写法多走了收缩循环，换来的是通用性——把判非法的条件从“某字符出现超过 1 次”换成“窗口内字符种类超过 k”或“窗口内 0 的个数超过 k”，同一套骨架就能解 340、424、1004 等题。这就是通用可变窗口模板的形状：扩张 → while(非法) 收缩 → 统计。

左右指针都只向右移动，每个下标最多入窗一次、出窗一次，所以仍然是线性。

解题步骤

初始化：count 计数表、left = 0、ans = 0。要牢记 count 描述的是当前窗口，不是整串的字符频次。

扩张：right 右移一位，count[s[right]]++。

判非法：本轮只有 ch = s[right] 的计数可能升到 2，所以只检查 count[ch] > 1 就够了，不必扫描整张表。

收缩：while (count[ch] > 1)，取出 s[left]，把它的计数减一，left++。循环退出时 ch 在窗口中只剩一个。

统计：窗口合法后用 right - left + 1 更新 ans。

返回 ans。

以 s = "pwwkew" 走一遍：p 得 [0,0]；w 得 [0,1]，ans=2；下标 2 的 w 使 count['w'] = 2，收缩两次（移出 p、移出下标 1 的 w），窗口变 [2,2]；k 得 [2,3]，ans=2；e 得 [2,4]，ans=3；下标 5 的 w 再次超标，收缩到 [3,5]，长度仍是 3。最终 ans = 3，对应子串 "wke"。注意 "pwke" 是子序列不是子串，这也是本题常见的读题陷阱。

代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> count = new HashMap<>();
        int left = 0;
        int ans = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            count.put(ch, count.getOrDefault(ch, 0) + 1);

            while (count.get(ch) > 1) {
                // 只收缩到本轮新增字符不重复，窗口就恢复合法。
                char removed = s.charAt(left);
                count.put(removed, count.get(removed) - 1);
                left++;
            }

            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}

func lengthOfLongestSubstring(s string) int {
    count := make(map[byte]int)
    left := 0
    ans := 0

    for right := 0; right < len(s); right++ {
        ch := s[right]
        count[ch]++

        for count[ch] > 1 {
            // 只收缩到本轮新增字符不重复，窗口就恢复合法。
            removed := s[left]
            count[removed]--
            left++
        }

        if right-left+1 > ans {
            ans = right - left + 1
        }
    }

    return ans
}

复杂度分析

时间复杂度：$O(n)$，每个下标最多被 right 加入一次、被 left 移出一次，收缩总次数不超过 n。

空间复杂度：$O(\min(n, k))$，计数表规模不超过窗口内出现过的字符种类数。

关键点总结

只检查“本轮新增字符”的计数，是把判非法从 $O(k)$ 降到 $O(1)$ 的关键。

count 的语义严格绑定当前窗口，移出左端点时必须同步减一，漏减会让窗口永远非法。

本题首推最近位置写法，更短且没有内层循环；计数写法的价值在于模板可迁移。

解法对比

最近出现位置：$O(n)$ 时间，一步跳过所有无效左边界，没有内层循环，代码最短，是本题面试主解。代价是必须理解“过期历史位置”，写漏 preIndex >= left 就会 WA。

字符计数：同样 $O(n)$，多了收缩循环、常数略大，但结构就是通用可变窗口模板。当约束换成“至多 k 种字符”“至多 k 个可替换字符”时跳跃法失效，计数法只需改一行判非法条件。

面试建议：先用最近位置版本拿下本题，再补一句“如果约束推广到至多 k 种字符，我会换成计数收缩的窗口模板”，可以同时体现熟练度和迁移能力。

常见面试追问：为什么代码里有内层 while 仍是 $O(n)$？因为 left 只向右走，每个字符最多入窗、出窗各一次；如果要求返回最长子串本身，只需在刷新 ans 时同步记录起点；如果输入可能包含多字节 Unicode，Go 版本要把 byte 窗口改成 []rune，否则一个字符会被拆成多个字节。

易错点总结

漏掉 preIndex >= left 判断：直接 left = preIndex + 1 会让 left 回退。用 "abba" 一测即错，返回 3 而正确答案是 2。

先更新 lastIndex 再取 preIndex：读到的是当前下标自己，preIndex >= left 恒成立，left 每轮都被推到 right + 1，窗口长度恒为 0，任何输入都返回 0。

在修复窗口之前更新答案：会把含重复字符的非法窗口长度计入，结果偏大。

把 ans 初始化为 1：空串会返回 1，正确初值是 0。

计数写法忘记同步减一：移出左端点时只做 left++ 而不减计数，while 条件永远成立，直接死循环。

把子序列当成子串："pwwkew" 的答案是 3 而不是 4，"pwke" 并不连续。

字符集假设：Java 的 char 与 Go 的 byte 处理常规 ASCII 没问题；若输入含多字节 Unicode，Go 按 byte 遍历会切开码点，需要改成 []rune。

相似题目

题目	难度	考察点
159. 至多包含两个不同字符的最长子串	中等	判非法条件换成窗口内字符种类超过 2
340. 至多包含 K 个不同字符的最长子串	中等	种类上限推广为 k，计数写法可直接复用
424. 替换后的最长重复字符	中等	合法条件变为「窗口长度 - 最高频次 ≤ k」
1004. 最大连续 1 的个数 III	中等	只对 0 计数，窗口内 0 的个数不超过 k
992. K 个不同整数的子数组	困难	恰好 k 种，拆成「至多 k」减「至多 k-1」
剑指 Offer 48. 最长不含重复字符的子字符串	中等	与本题同题，另可用「以 i 结尾」的 dp 视角推导