跳至主要內容

无重复字符的最长子串：滑动窗口入门到竞赛级模板

老张2026/4/30大约 12 分钟

无重复字符的最长子串：滑动窗口入门到竞赛级模板

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约20分钟 | 难度：Medium

开篇故事

2020年我在一个电商项目里遇到了一个实际问题：用户的搜索词分析。产品要求找出用户搜索词中"没有重复字符的最长片段"，用来评估搜索词的多样性。当时我同事老李直接写了个 O(n²) 的嵌套循环，上线后每次分析百万级搜索词日志，这个函数跑了将近 7 秒。

我看到这个耗时，本能地就问：「你有没有想过滑动窗口？」老李摇摇头，说不太熟悉。我花了两个小时给他讲了滑动窗口的思路，他自己改了代码，最终同样的分析从 7 秒降到了不到 100 毫秒。

这个真实经历让我对这道题有了不一样的感情。LeetCode 3 是我认为所有 Java 工程师必须彻底掌握的题目之一，不只是因为它是面试高频题，更因为"滑动窗口"这个模式在工程里真的有用。流量监控、日志分析、字符串处理……到处能见到它的影子。

这道题的难点有两个：第一，理解滑动窗口的"窗口收缩"时机；第二，如何高效地维护窗口内的字符状态。很多人第一次做都是写出了 O(n²) 甚至 O(n³) 的暴力解，没有真正理解窗口的核心逻辑。

一、题目解析

LeetCode 3. 无重复字符的最长子串（Longest Substring Without Repeating Characters）

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

输入输出示例：

示例 1（基础情况）：

输入：s = "abcabcbb"
输出：3
解释：无重复字符的最长子串是 "abc"，长度为 3

示例 2（全部相同字符）：

输入：s = "bbbbb"
输出：1
解释：无重复字符的最长子串是 "b"，长度为 1

示例 3（无重复字符）：

输入：s = "pwwkew"
输出：3
解释：无重复字符的最长子串是 "wke"，长度为 3
注意："pwke" 是子序列而不是子串，顺序必须连续

边界情况 4（空字符串）：

输入：s = ""
输出：0

边界情况 5（单字符）：

输入：s = "a"
输出：1

考察的核心知识点：

  • 滑动窗口（双指针的特殊形式）
  • 哈希表/数组维护窗口内字符状态
  • 窗口的扩展与收缩逻辑
  • 最大值的维护时机

二、解法一：暴力解法

思路分析

枚举所有子串的起始位置 i 和结束位置 j，判断子串 s[i..j] 是否没有重复字符，记录最大长度。

判断一个子串是否有重复字符：用一个 HashSet 遍历子串中每个字符，如果 add 返回 false（已存在），说明有重复。

三层嵌套：外层枚举 i（O(n)），中层枚举 j（O(n)），内层判断是否有重复（O(n)），总时间 O(n³)。可以优化成两层：外层枚举起点 i，内层从 i 开始一个个添加字符，遇到重复就 break，这样是 O(n²)。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLen = 0;
        
        // 枚举子串起点
        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            // 从 i 开始向右扩展，直到遇到重复字符
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (seen.contains(c)) {
                    // 遇到重复字符，当前起点的最长子串已确定
                    break;
                }
                seen.add(c);
                // 更新最大长度
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
        return maxLen;
    }
}

复杂度分析

时间复杂度：O(n²)

外层 O(n)，内层最坏情况也是 O(n)（无重复字符时跑到底），总体 O(n²)。

空间复杂度：O(min(n, m))

m 是字符集大小（ASCII 字符集 m=128，Unicode 更大）。HashSet 最多存 min(n, m) 个字符。

缺陷： 每次换起点都要重新建 HashSet，做了大量重复工作。从 i=0 开始能达到的最长无重复子串，很多字符状态可以在 i 递进时复用。这正是滑动窗口要解决的问题。

三、解法二：滑动窗口+HashSet

优化思路

暴力的问题：每次移动起点都重置了所有状态，没有利用上一轮的信息。

观察一下：如果窗口 [left, right] 是当前无重复子串，当我们把 right 右移到 right+1 时，如果 s[right+1] 不在窗口里，直接扩大窗口；如果在窗口里，就需要把 left 右移，直到把那个重复字符移出窗口。

这就是滑动窗口的精髓：窗口的右边界尽量往右扩，遇到冲突时从左边界收缩，直到冲突消失。整个过程中，right 只往右走，left 也只往右走（因为没有必要往回走），所以总共只有 O(n) 次操作。

用 HashSet 维护窗口内的字符集合：扩展时 add，收缩时 remove。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> window = new HashSet<>();
        int left = 0, right = 0;
        int maxLen = 0;
        
        while (right < n) {
            char c = s.charAt(right);
            
            // 如果右边界字符已在窗口中，收缩左边界
            while (window.contains(c)) {
                window.remove(s.charAt(left));
                left++;
            }
            
            // 扩展右边界
            window.add(c);
            maxLen = Math.max(maxLen, right - left + 1);
            right++;
        }
        
        return maxLen;
    }
}

复杂度分析

时间复杂度：O(n)

right 指针从 0 走到 n-1，共 n 步。left 指针也是从 0 向右单调移动，总共移动次数不超过 n 次。所以 left 和 right 合计移动 2n 次，每次操作 O(1)，总体 O(n)。

空间复杂度：O(min(n, m))

窗口最大是字符集大小 m（ASCII 是 128）。

这个解法已经是 O(n)，但还有优化空间。注意内层 while 循环：遇到重复字符时，left 一个一个往右移，直到重复字符离开窗口。这个过程在最坏情况下（比如 "abcdefgha"，最后遇到 'a' 时要把左边界从 0 移到 1）也是 O(n) 次小操作，但总体均摊下来仍是 O(n)。不过我们可以做得更精准——直接跳过重复字符的位置。

四、解法三：滑动窗口+HashMap（竞赛级最优）

核心洞见

上面 HashSet 的方案每次都要一步一步地从 left 移除元素。能不能直接"跳跃"到重复字符的下一个位置？

可以。只需要用 HashMap 记录每个字符最后一次出现的下标。当 s[right] 在窗口内出现过，并且上次出现的位置是 lastIndex，那么 left 可以直接跳到 lastIndex + 1，不需要一步步移动。

但有个细节：left 只能往右走，不能往左退。所以更新时要取 Math.max(left, lastIndex + 1)，防止 left 倒退（这在某些字符出现在窗口左边界之外时会发生）。

算法流程

完整 Java 代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // key: 字符, value: 该字符最后出现的下标
        Map<Character, Integer> lastIndex = new HashMap<>();
        int left = 0;  // 窗口左边界
        int maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            
            // 如果字符 c 在当前窗口内（即它的上次出现位置 >= left）
            // 则需要把 left 移到上次出现位置的下一位
            if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
                // 关键：left 只能往右走，不能倒退
                left = lastIndex.get(c) + 1;
            }
            
            // 更新字符 c 的最新下标
            lastIndex.put(c, right);
            
            // 更新最大窗口长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

复杂度分析

时间复杂度：O(n)

只有一个 for 循环，每次循环做 O(1) 的 HashMap 操作。left 的更新是 O(1) 的跳跃，不是逐步移动。总体严格 O(n)，没有隐藏的内层循环。

空间复杂度：O(min(n, m))

HashMap 最多存 min(n, m) 个字符，m 是字符集大小。

我在 LeetCode 提交这个版本，运行时间 3ms，击败 98.5% 的 Java 用户。相比 HashSet 版本快了不少，主要是避免了内层 while 循环的多次移除操作。

进一步优化： 如果输入只包含 ASCII 字符（题目约束中字符范围是 0-127），可以用 int[128] 代替 HashMap，初始化为 -1，这样能省掉哈希计算开销，速度更快：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 用数组代替 HashMap，适用于 ASCII 字符集
        int[] lastIndex = new int[128];
        Arrays.fill(lastIndex, -1);  // -1 表示未出现过
        
        int left = 0;
        int maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            int c = s.charAt(right);
            
            // 如果字符在当前窗口内出现过
            if (lastIndex[c] >= left) {
                left = lastIndex[c] + 1;
            }
            
            lastIndex[c] = right;
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

这个版本在 LeetCode 上运行时间 1ms，击败了 99.7% 的 Java 用户。

五、举一反三

同类型题目

LeetCode 159. 至多包含两个不同字符的最长子串（付费题）

窗口内最多允许 2 种不同字符。用 HashMap 记录窗口内每种字符的出现次数，字符种类数超过 2 时收缩左边界。

LeetCode 340. 至多包含 K 个不同字符的最长子串（付费题）

把上面的 2 改为 K，是通用化版本。

LeetCode 76. 最小覆盖子串

下一篇的主题，滑动窗口的困难级应用。窗口要包含 t 中所有字符，找最小窗口。

LeetCode 424. 替换后的最长重复字符

窗口内最多替换 k 个字符，使窗口变成全部相同字符的字符串，求最大窗口长度。

滑动窗口通用模板

// 滑动窗口模板（适用于大多数子串问题）
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int result = 0; // 或者 Integer.MAX_VALUE，视题意

while (right < s.length()) {
    char c = s.charAt(right++);
    // 1. 更新窗口状态（右边界扩展）
    window.merge(c, 1, Integer::sum);
    
    // 2. 判断是否需要收缩（窗口不合法时）
    while (窗口不合法) {
        char d = s.charAt(left++);
        // 更新窗口状态（左边界收缩）
        window.merge(d, -1, Integer::sum);
        if (window.get(d) == 0) window.remove(d);
    }
    
    // 3. 更新结果（窗口合法时）
    result = Math.max(result, right - left);
}
return result;

面试中的变体和追问

  1. 如果字符串包含 Unicode 字符怎么处理？ 答：用 HashMap 而不是数组，Character 作为 key。数组大小不够容纳 Unicode 全集。

  2. 窗口大小固定的滑动窗口怎么写？ 答：那是"固定窗口"，right - left == k 时收缩左边界。本题是"不定长窗口"，通过合法性判断来决定是否收缩。两种模式要区分清楚。

  3. 这道题和双指针有什么关系？ 答：滑动窗口就是双指针的一种特殊形式，两个指针都向同一方向移动（right 扩张，left 收缩），形成一个"窗口"。区别于头尾相对的双指针。

六、踩坑实录

坑一：HashMap 方案中 left 倒退

现象： 输入 "abba"，期望输出 2（"ab" 或 "ba"），但代码输出了 3。

原因： 遍历到第二个 a（下标 3）时，HashMap 里 a 的上次下标是 0，left = 0 + 1 = 1，正确。但是，如果先遍历到第二个 b（下标 2），HashMap 里 b 的上次下标是 1，left = 1 + 1 = 2，正确。然后遍历到第二个 a（下标 3），HashMap 里 a 的上次下标是 0，left = 0 + 1 = 1，这就比当前的 left=2 还小了，left 倒退了！

解法： 更新 left 时必须取最大值：left = Math.max(left, lastIndex.get(c) + 1)。这保证 left 只往右走不往左退。

坑二：空字符串和单字符的处理

现象： 输入 "" 时抛出异常，或者返回了 -1、1 等错误值。

原因： 忘记处理空字符串。for 循环在 s.length() == 0 时不执行，maxLen 初始为 0，返回 0，这个行为是正确的。大多数情况下 Java 代码不需要特判空字符串，但要确保初始值是 0 而不是 -1 或 Integer.MIN_VALUE。

解法： maxLen 初始化为 0，不需要特判空字符串。

坑三：用 charAt vs toCharArray 的性能陷阱

现象： 代码逻辑正确，但在 LeetCode 上性能不如预期。

原因： 在循环里频繁调用 s.charAt(right) 是没问题的，但如果同时还要操作 s.charAt(left) 等多个位置，多次调用 charAt 有一定开销。在极度性能敏感的场景下，可以先 char[] cs = s.toCharArray() 转成数组，后续访问 cs[i] 比 s.charAt(i) 快（避免了方法调用开销和边界检查）。

实际上这只是微优化，差距很小。LeetCode 的时间测量有波动，不必过分纠结这个。

七、总结

滑动窗口是字符串和数组问题里最重要的算法模式之一。这道题从 O(n²) 暴力到 O(n) 哈希窗口，背后的核心是两个洞见：

三条核心要点：

  1. 滑动窗口的本质是：right 负责扩展，left 负责在违规时收缩，两个指针都只往右走，所以总体是 O(n) 而不是 O(n²)。理解这一点，才算真正懂了滑动窗口。

  2. HashMap 版本比 HashSet 版本更优，原因是 HashMap 记录了每个字符的位置，可以直接跳跃到重复字符的下一位置，避免了逐步移动 left 的内层 while 循环。

  3. left 只能往右走，更新时用 Math.max(left, newPos) 防止倒退，这个细节很容易忘。

延伸思考：

滑动窗口框架可以解决大量"连续子数组/子串的最值"问题。关键是定义清楚什么是"合法窗口"，以及"扩展"和"收缩"时需要维护哪些状态。掌握了这道题，再去做 LeetCode 76（最小覆盖子串）会顺畅很多。

编辑此页
最近更新:
贡献者: xiaozhangge