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

标签#

平台：LeetCode
难度：中等
数据结构：字符串、集合、哈希表
算法：滑动窗口、双指针
解题模式：可变窗口、同向双指针

一、题目概述#

给定一个字符串，求其中不包含重复字符的最长连续子串长度。当前仓库的主方法使用集合维护滑动窗口；源码中还保留了一个基于哈希表记录最近下标的内部类实现。

二、解题思路#

主方法使用可变滑动窗口。右指针 right 逐个扩展窗口，window 集合保存当前窗口中的字符。如果当前字符已经存在于窗口中，说明窗口出现重复，需要不断移动左指针 left，并从集合中移除左侧字符，直到窗口中不再包含当前字符。

每次把当前字符加入窗口后，用 right - left + 1 更新最大长度。

三、执行过程#

创建 HashSet<Character> 作为当前窗口。
初始化 left = 0 和 maxLength = 0。
right 从左到右遍历字符串。
如果 currentChar 已在窗口中，持续移除 s.charAt(left) 并右移 left。
将 currentChar 加入窗口。
用当前窗口长度更新最大值。
遍历结束后返回 maxLength。

例如 s = "abcabcbb"：窗口依次扩展到 "abc" 时最大长度为 3；再次遇到 a 后左边界右移，继续维护无重复窗口。

四、代码实现#

1
public class LeetCode0003LengthOfLongestSubstring {
2

3
    public int lengthOfLongestSubstring(String s) {
4
        HashSet<Character> window = new HashSet<>();
5
        int maxLength = 0;
6
        int left = 0;
7

8
        for (int right = 0; right < s.length(); right++) {
9
            char currentChar = s.charAt(right);
10

11
            while (window.contains(currentChar)) {
12
                window.remove(s.charAt(left));
13
                left++;
14
            }
15

16
            window.add(currentChar);
17
            maxLength = Math.max(maxLength, right - left + 1);
18
        }
19

20
        return maxLength;
21
    }
22
}

源码中还保留了一个内部类 LongestSubstringWithoutRepeatingCharacters，它使用 Map<Character, Integer> 记录字符最近一次出现位置，并通过 Math.max(left, lastIndex + 1) 防止左边界回退。

五、关键代码说明#

window：保存当前滑动窗口内的字符，判断是否重复。
left：窗口左边界，只会向右移动。
right：窗口右边界，负责逐个扫描字符串。
while (window.contains(currentChar))：当窗口出现重复字符时收缩窗口。
maxLength：记录扫描过程中出现过的最大无重复窗口长度。

六、复杂度分析#

时间复杂度：O(n)，每个字符最多被右指针加入一次、被左指针移除一次。
空间复杂度：O(k)，其中 k 是窗口内不同字符数量，最坏情况下为 O(n)。

七、注意事项#

当前主方法没有处理 s == null，测试中也明确传入 null 会抛出 NullPointerException。
收缩窗口时必须使用 while，因为左侧可能需要连续移除多个字符。
内部类的哈希表版本虽然能处理 null 和空字符串，但当前测试调用的是外层主方法。

八、面试知识点：滑动窗口与 HashSet#

1. 为什么这题适合滑动窗口？#

题目要求的是“连续子串”，而不是子序列。连续区间问题经常可以考虑滑动窗口。

本题窗口要维护的性质是：窗口内不能有重复字符。右指针负责扩大窗口，左指针负责在出现重复时收缩窗口。整个过程始终维护一个无重复字符的连续区间。

2. 什么是可变滑动窗口？#

滑动窗口一般分为固定窗口和可变窗口。

固定窗口：窗口长度固定，例如每次看长度为 k 的子数组；
可变窗口：窗口长度会根据条件变化，例如本题遇到重复字符时收缩窗口。

本题属于可变窗口，因为窗口大小不是固定的，而是由“是否包含重复字符”这个条件决定。

3. HashSet 在本题中存什么？#

当前实现使用：

1
HashSet<Character> window = new HashSet<>();

window 保存当前窗口中的所有字符，用于快速判断 currentChar 是否已经出现。

如果 window.contains(currentChar) 为 true，说明当前窗口加入这个字符后会重复，需要移动左边界并删除左侧字符，直到窗口中不再包含 currentChar。

4. 为什么出现重复时要用 while？#

出现重复字符时，左边界可能需要连续移动多次。

例如 s = "abba"：

窗口先扩展到 "ab"；
再遇到第二个 b，需要移除 a，窗口仍然包含 b；
还要继续移除第一个 b，才能加入当前 b。

所以这里必须使用 while，不能只用 if。

5. 为什么左右指针都只向右移动？#

滑动窗口的效率来自这一点：每个字符最多被右指针加入一次，最多被左指针移除一次。

虽然代码里有嵌套的 while，但整体不是 O(n^2)。因为左指针不会回退，所有移除操作加起来最多也是 n 次，所以总时间复杂度是 O(n)。

6. HashSet 和 HashMap 有什么关系？#

面试中常会从 HashSet 追问到 HashMap。

可以这样理解：HashSet 只关心元素是否存在，不关心映射值；HashMap 保存 key-value 映射。Java 中 HashSet 的底层通常借助 HashMap 实现，把元素作为 key，value 使用一个固定占位对象。

所以本题如果只需要判断字符是否在窗口中，使用 HashSet 就够了；如果还想快速跳过重复字符上一次出现的位置，可以使用 HashMap<Character, Integer>。

7. HashSet 版本和 HashMap 版本有什么区别？#

当前主方法是 HashSet 版本，重复时通过 while 一个个移除左侧字符。

源码内部类中还有一个 HashMap 版本，记录每个字符最近一次出现位置。遇到重复字符时，可以直接把 left 移动到上次出现位置的后一位：

1
left = Math.max(left, lastIndexMap.get(currentChar) + 1);

这个 Math.max 很关键，用来防止 left 回退。例如 abba 中最后一个 a 的上次位置在窗口外，不能把左边界重新移回去。

8. char 能表示所有字符吗？#

Java 的 char 是 UTF-16 代码单元，不一定能完整表示所有 Unicode 字符。某些特殊字符可能需要两个 char 组成。

LeetCode 这类题通常默认输入是常规字符集，因此用 charAt 和 Character 足够。如果面试官追问 Unicode 完整处理，可以说明需要按 code point 遍历，而不是简单按 char 遍历。

9. 滑动窗口题的通用思路是什么？#

可以按这个模板思考：

明确窗口表示什么；
明确窗口需要满足什么条件；
右指针扩展窗口；
条件不满足时，左指针收缩窗口；
在合适时机更新答案。

本题中，窗口表示当前无重复字符子串；条件是窗口内不含重复字符；答案是窗口长度最大值。

10. 回到本题，面试时怎么回答？#

可以这样组织回答：

这道题要求最长的无重复连续子串，所以我使用滑动窗口。窗口用 HashSet 保存当前区间内的字符，右指针不断向右扩展。如果当前字符已经在集合中，就说明窗口出现重复，需要移动左指针，并从集合中移除左侧字符，直到窗口内不再包含当前字符。然后加入当前字符并更新最大长度。
虽然代码里有 while 收缩窗口，但每个字符最多被加入一次、移除一次，所以总时间复杂度是 O(n)。空间复杂度取决于窗口内不同字符数量，最坏是 O(n)。如果想进一步优化左指针移动，可以用 HashMap 记录字符最近出现位置。