题目描述

LeetCode 3. 无重复字符的最长子串

给定一个字符串 s，请你找出其中不含有重复字符的连续最长子串的长度。

示例

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
​
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
​
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
（注意："pwke" 是一个子序列，不是连续子串）

学习历程（从暴力到优化）

第一步：分析暴力解法

第一反应：双重循环枚举所有子串，检查是否有重复字符。

for i in range(n):
    for j in range(i, n):
        检查 s[i..j] 是否有重复
        如果没有，更新最大长度

复杂度分析:

  • 时间复杂度：O(n³)（两层循环 + 检查重复的 O(n)）

  • 空间复杂度：O(字符集大小)

问题：太慢了，有大量重复检查。

第二步：联想滑动窗口

思考：当 i=0 时，j 从 0 向右走到第一个重复字符为止。当 i=1 时，j 能不能不用回退到 i+1？

洞察：可以！j 已经走过的路，前面的字符是否重复我们是知道的。只需要移动左边界 i，j 继续向右即可。

这就是滑动窗口：维护一个 [i, j] 的窗口，保证窗口内没有重复字符。

第三步：滑动窗口的核心机制

两个指针：

  • i：左指针（窗口左边界）

  • j：右指针（窗口右边界），只往右走，不回退

执行流程：

  1. j 向右移动，尝试把 s[j] 纳入窗口

  2. 如果 s[j] 已经在窗口内出现过，把 i 右移到上次重复字符的下一个位置

  3. 更新当前窗口的最大长度

为什么 j 不需要回退？

  • 因为 i 向右移动后，窗口 [i, j] 已经是一个合法的无重复子串。

  • j 之前的位置已经被检查过了，不可能产生更长的结果。

第四步：哈希表的作用

哈希表记录什么？

  • map[字符] = 该字符最近一次出现的下标

两个核心作用：

  1. O(1) 查询重复：判断 s[j] 是否在窗口内出现过

  2. O(1) 定位左边界：直接拿到上次出现的位置，计算 i 的新位置

注意：每次 j 移动后，必须更新哈希表中该字符的位置为 j，否则下次查询会拿到过期的位置。

第五步：左边界更新的关键公式

i = Math.max(i, map.get(c) + 1);

为什么不能直接写 i = map.get(c) + 1？

反例：s = "abba"

  • j=0：'a'，i=0

  • j=1：'b'，i=0

  • j=2：'b'，上次在 1，i = max(0, 2) = 2

  • j=3：'a'，如果不用 max，上次在 0，i = 0 + 1 = 1 → i 往回走了！

    • 但此时窗口 [2,2] 才是合法的，i 不能回退到 1

所以用 max 保证 i 只增不减。

第六步：手动推导验证

以 s = "pwwkew" 为例：

j

s[j]

查表位置

i = max(i, 查表+1)

更新表

窗口 [i,j]

长度

maxLen

0

p

无

0

p→0

p

1

1

1

w

无

0

w→1

pw

2

2

2

w

1

max(0, 2)=2

w→2

w

1

2

3

k

无

2

k→3

wk

2

2

4

e

无

2

e→4

wke

3

3

5

w

2

max(2, 3)=3

w→5

kew

3

3

最终答案 maxLen = 3 ✓

完整代码实现（Java）

import java.util.HashMap;
import java.util.Map;
​
public class LengthOfLongestSubstring {
​
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLen = 0;
        int i = 0;  // 左指针
​
        // HashMap: 字符 -> 最近一次出现的下标
        Map<Character, Integer> map = new HashMap<>();
​
        for (int j = 0; j < n; j++) {
            char c = s.charAt(j);
​
            // 如果字符出现过，更新左边界
            if (map.containsKey(c)) {
                i = Math.max(i, map.get(c) + 1);
            }
​
            // 更新该字符的最新位置
            map.put(c, j);
​
            // 更新最大长度
            maxLen = Math.max(maxLen, j - i + 1);
        }
​
        return maxLen;
    }
​
    // 测试
    public static void main(String[] args) {
        LengthOfLongestSubstring solution = new LengthOfLongestSubstring();
​
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb"));  // 3
        System.out.println(solution.lengthOfLongestSubstring("bbbbb"));     // 1
        System.out.println(solution.lengthOfLongestSubstring("pwwkew"));    // 3
    }
}

复杂度分析

指标

复杂度

说明

时间复杂度

O(n)

j 遍历一次，i 最多也移动 n 次

空间复杂度

O(min(n, 字符集大小))

HashMap 最多存储字符集大小的键值对

关键总结

解题模板（滑动窗口 + 哈希表）

1. 初始化左指针 i = 0，结果 maxLen = 0
2. 右指针 j 从左到右遍历字符串
3. 如果 s[j] 出现过，i = max(i, 上次位置 + 1)
4. 更新哈希表中 s[j] 的位置为 j
5. 更新 maxLen = max(maxLen, j - i + 1)

类似题目

题目

核心思想

最小覆盖子串

滑动窗口 + 字符计数

找到字符串中所有字母异位词

滑动窗口 + 固定窗口大小

最长重复子数组

动态规划 / 滑动窗口

替换后的最长重复字符

滑动窗口 + 字符频率统计

面试技巧

  1. 先讲暴力解：双重循环，至少能得部分分

  2. 引导到滑动窗口：强调 j 不回退，把 O(n²) 优化到 O(n)

  3. 解释 max(i, 上次位置+1)：这是面试官最爱追问的细节

  4. 提到哈希表必须更新：体现对边界条件的敏感

  5. 手动推导一个例子：用 "pwwkew" 或 "abba" 验证逻辑

易错点复盘

  1. 忘记更新哈希表：导致下次查询拿到过期位置，i 计算错误

  2. i 没有用 max：导致 i 往回走，窗口内出现重复字符

  3. 长度公式写错：是 j - i + 1，不是 j - i 或 j - i - 1

  4. if (map.containsKey(c)) 不能省略：否则 map.get(c) 返回 null 会 NPE

  5. 混淆子串和子序列：子串必须连续，子序列不要求连续