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

《二哥的 LeetCode 刷题笔记》真的经典。

————————by 鲁迅

题意

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

示例

输入: s = "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

难度

中等

分析 1

看完这道题目的描述，脑袋里面要先搞清楚几个概念：

• 什么是子串？

• 什么是最长子串？

• 什么是不含重复字符的最长子串？

这三个概念搞清楚，才能去写题解，对吧？

什么是子串？拿题目给出的示例来说，abcabcbb，它的子串有：

a、b、c、a、b、c、b、b 这种单个子串

ab、bc、ca、cb、bb 这种两个字符组成的子串

abc、bca、cab、bcb、cbb 这种三个字符组成的子串

abca、bcab、cabc、abcb 这种四个字符组成的子串

abcab、bcabc、cabcb、abcbb 这种五个字符组成的子串

abcabc、bcabcb、cabcbb 这种六个字符组成的子串

abcabcb bcabcbb 这种七个字符组成的子串

abcabcbb 这种八个字符组成的子串

什么是最长子串？

就是子串中字符个数最多的那个子串，比如上面的例子中，abcabcbb 就是最长子串。

什么是不含重复字符的最长子串？

就是最长子串中没有重复字符的那个子串，abcabcbb 虽然是最长子串，但有重复字符 a、

b、c，所以不是不含重复字符的最长子串。

abcabcb 也不是，因为有重复字符 a、b、c。

abcabc 也不是，因为有重复字符 a、b、c。

abcab 也不是，因为有重复字符 a、b。

abca 也不是，因为有重复字符 a。

排除到最后，你会发现，不含重复字符的最长子串有这么几个：

abc、bca、cab

OK，答案出来了，长度为 3。

借着这个思路，我们直接来暴力解题。

class Solution {

public int lengthOfLongestSubstring(String s) {

int res = 0; // 用于存储最长子串的长度

// 外层循环，从字符串的第一个字符开始

for (int i = 0; i < s.length(); i++) {

boolean[] book = new boolean[300]; // 布尔数组，用于标记字符是否出现过

// 内层循环，从当前字符向前遍历

for (int j = i; j >= 0; j--) {

// 如果字符已经在子串中出现过，结束内层循环

if (book[s.charAt(j)])

break;

// 标记当前字符为出现过

book[s.charAt(j)] = true;

// 更新最长子串的长度

res = Math.max(res, i - j + 1);

}

}

return res; // 返回最长子串的长度

}

}

两层循环，第一层循环用来确定起始位置，第二层循环用来确定结束位置，向前去找最长

的子串，如果字符出现过，我们就标记它为 true，并且计算最长子串的长度。

①、题目说 s 由英文字母、数字、符号和空格组成，那么它很可能是 ASCII 码字符集，在

ASCII 字符集中，有 128 个不同的字符，这包括了大小写英文字母（52 个）、数字（10

个）、标点符号和特殊字符（如空格、制表符等），以及一些控制字符。

那为了节省空间，数组 book 的长度其实可以声明为 128，而不是 300。

boolean[] book = new boolean[128]; // 足以覆盖所有 ASCII 字符

当然了，笔试的时候时间紧张，如果没办法考虑周全的话，300 肯定是一个保险的方案，

确保出现的字符都能够容纳得下。

②、i - j + 1 用来计算子串的长度，这里的 i 是外层循环的循环变量，j 是内层循环的循环

变量，i - j + 1 就是子串的长度。

• i 是子串末尾字符的索引。

• j 是子串起始字符的索引。

• i - j 是子串起始和结束字符之间的距离（即子串的长度减去 1）。

• 加上 1 (i - j + 1) 是为了包含起始字符在内的整个子串的长度。

在例子 “abcabcbb” 中，当我们考虑以第一个 ‘b’（索引 1）结尾的子串时：

• 当 i = 1（‘b’ 的位置）和 j = 1（仍然是 ‘b’ 的位置）时，i - j + 1 = 1，表示子串 “b” 的长

度。

• 当 i = 1 和 j = 0（‘a’ 的位置）时，i - j + 1 = 2，表示子串 “ab” 的长度。

当字符串 s = "abcabcbb" 时，我们用该题解来模拟一下整个题解的过程。

1. 初始化：最长子串长度 res = 0。

2. 开始外层循环：逐字符遍历字符串 s。

– i = 0（字符 ‘a’）：

• 初始化 book 数组，其中所有值均为 false。

• 内层循环：从 j = 0 开始向前遍历。

– 检查 ‘a’ 是否已经出现过（book[s.charAt(0)]），结果为 false。

– 标记 ‘a’ 为出现过（book['a'] = true）。

– 更新 res 为 max(res, i - j + 1)，即 max(0, 0 - 0 + 1) = 1。

– 退出内层循环。

– 注意：这里的子串是 “a”，长度为 1。

– i = 1（字符 ‘b’）：

• 初始化 book 数组，其中所有值均为 false。

• 内层循环：从 j = 1 开始向前遍历。

– 检查 ‘b’ 是否已经出现过，结果为 false。

– 标记 ‘b’ 为出现过。

– 更新 res 为 max(1, 1 - 1 + 1) = 1。

• 内层循环：j = 0。

– 检查 ‘a’ 是否已经出现过，结果为 false。

– 标记 ‘a’ 为出现过。

– 更新 res 为 max(1, 1 - 0 + 1) = 2。

– 退出内层循环。

– 注意：这里的子串是 “ab”，长度为 2。

– i = 2（字符 ‘c’）：

• 初始化 book 数组，其中所有值均为 false。

• 内层循环：从 j = 2 开始向前遍历。

– 检查 ‘c’ 是否已经出现过，结果为 false。

– 标记 ‘c’ 为出现过。

 – 更新 res 为 max(1, 2 - 2 + 1) = 1。

• 内层循环：j = 1

– 检查 ‘b’ 是否已经出现过，结果为 false。

– 标记 ‘b’ 为出现过。

– 更新 res 为 max(1, 2 - 1 + 1) = 2。

• 内层循环：j = 0

– 检查 ‘a’ 是否已经出现过，结果为 false。

– 标记 ‘a’ 为出现过。

– 更新 res 为 max(2, 2 - 0 + 1) = 3。

– 退出内层循环。

– 注意：这里的子串是 “abc”，长度为 3。

– i = 3（第二个字符 ‘a’）：

• 初始化 book 数组，其中所有值均为 false。

• 内层循环：从 j = 3 开始向前遍历。

– 检查 ‘a’ 是否已经出现过，结果为 false。

– 标记 ‘a’ 为出现过。

– 更新 res 为 max(3, 3 - 3 + 1) = 1。

• 内层循环：j = 2

– 检查 ‘c’ 是否已经出现过，结果为 false。

– 标记 ‘c’ 为出现过。

– 更新 res 为 max(3, 3 - 2 + 1) = 2。

• 内层循环：j = 1

– 检查 ‘b’ 是否已经出现过，结果为 false。

– 标记 ‘b’ 为出现过。

– 更新 res 为 max(3, 3 - 1 + 1) = 3。

• 内层循环：j = 0

– 检查 ‘a’ 是否已经出现过，结果为 true。

– 退出内层循环。

– 注意：这里的子串是 “bca”，长度为 3。

– 继续外层循环，重复以上过程，直到 i 遍历完整个字符串。

3. 结束遍历：所有字符都已被检查。

4. 返回结果：最长无重复字符子串的长度 res。在这个例子中，最长的无重复字符子串

长度为 3。

对 for 循环或者 break 比较陌生的球友，可以通过 ACM 的模式在 Intellij IDEA 中 debug 以

下，瞬间就明白了。

public class Main003 {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("输入字符串: ");

String s = scanner.nextLine(); // 从标准输入读取字符串

 Solution solution = new Solution();

int length = solution.lengthOfLongestSubstring(s); // 调用解题函数

System.out.println("没有重复的最长子串为: " + length); // 输出结果

}

}

class Solution {

public int lengthOfLongestSubstring(String s) {

int res = 0;

for (int i = 0; i < s.length(); i++) {

boolean[] book = new boolean[128]; // ASCII 字符集

for (int j = i; j >= 0; j--) {

if (book[s.charAt(j)]) {

break;

}

book[s.charAt(j)] = true;

res = Math.max(res, i - j + 1);

}

}

return res;

}

}

好，虽然通过两层循环也能解出来，但是这种暴力解法的时间复杂度是 $ O(n^2) $，效率

不高，我们需要想办法优化一下。

003.%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E

6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2-20231212144058.png

分析 2

接下来，我们介绍一个在 Java 中被隐藏起来的概念——指针，在 C/C++中，指针是一种

特殊的变量类型，用来记录变量的值在内存中的位置。

在数据结构中，也有一个指针的概念，但它和 C/C++中的指针不太一样，虽然它也指向一

个的位置，但并非指向存储值的物理位置，而是指向其在数据结构中的相对位置，就如同

Java 中熟知的下标（索引）一样，我们来看一段熟悉的代码：

for(int i = 1;i <= n;i++)

a[i] = 1;

上面的代码中，i 其实就是一个指针，被我们用来表示数组 a 中 1 到 n 的位置，实际上这

就是数据结构中指针的概念。

再来看这段代码，在二分查找中：

int lef = 1, rig = n;

while(lef < rig) {

int mid = (lef + rig) / 2; // 计算中间位置

if(a[mid] < goalVal)

lef = mid; // 如果中间位置的值小于目标值，调整左边界

else

rig = mid; // 如果中间位置的值大于或等于目标值，调整右边界

}

这里面的 lef,rig,mid 其实都是指针，指向数组中的某个位置，然后再用 a[]（a 是一个数

组）来取出这个位置的元素进行判断。

我们再来横向比较一下引用、指针、下标这些容易混淆的概念：

1704112042617-bfa534ce-1182-4de8-aae0-72ae4198ea4b.png

明白这一点，我们再来讲一个算法中经常出现的概念——滑动窗口。

题目要我们求解的是一个区间，所以我们可以考虑这样两个指针，一个指向这个区间的开

头，另外一个则指向这个区间的结尾。

我们让头指针不动，向后扩展尾指针，直到遇见重复元素（见下图）：

003.%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E

6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2-20231212154050.png

图片出自 LeetCode 的一个作者 Ikaruga

否则，向后移动头指针，重复之前的动作。

一个位置一个位置移动，也太低效了，有没有更好的办法呢？

我们可以用一个 HashMap 来存储每个字符的位置，这样我们就可以直接跳到这个字符上

次出现的位置，而不用一个一个地移动头指针了。

那由头指针和尾指针组成的区间，我们称之为滑动窗口。我用图简单来画一下大家就明白

了。

003.%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E

6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2-20231212165506.png

学过计算机网络的同学，应该都知道滑动窗口协议，用于网络数据传输时的流量控制，以

避免网络拥塞。算法中的滑动窗口主要用来解决数组/字符串的子元素问题，比如今天这

道题目，在字符串中寻找最长不含重复字符的子串。

003.%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E

6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2-20231212155932.png

推荐阅读资料：博客园上这篇关于滑动窗口的帖子写的非常不错

我们来看一下滑动窗口的题解：

class Solution {

public int lengthOfLongestSubstring(String s) {

HashMap<Character, Integer> rempos = new HashMap<>(); // 创建一个哈希

表来记录字符最近一次出现的位置

int res = 0; // 用于存储最长子串的长度

// 初始化两个指针 i 和 j，表示当前考虑的子串的头和尾

for (int i = 0, j = 0; i < s.length(); i++) {

// 检查当前字符是否出现过

if (rempos.containsKey(s.charAt(i))) {

// 如果出现过，则更新 j 的位置为该字符上次出现位置的下一个位置

// 保证子串 [j, i] 不包含重复字符

j = Math.max(j, rempos.get(s.charAt(i)));

}

// 更新最长子串的长度

res = Math.max(res, i - j + 1);

// 更新当前字符的位置信息

rempos.put(s.charAt(i), i + 1);

}

 return res; // 返回最长子串的长度

}

}

滑动窗口方法只需要一次遍历：

• 使用两个指针（通常称为头指针和尾指针）创建一个动态的窗口。这个窗口代表当前

考虑的子串。

• 移动尾指针：逐个检查字符，扩展窗口。

• 移动头指针：一旦遇到重复字符，就移动头指针，缩小窗口直到子串中不再包含重复

字符。

003.%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E

6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2-20231212170221.png

使用 HashMap 记录每个字符最近一次出现的位置（rempos.put(s.charAt(i), i + 1)）。

一旦出现重复字符（rempos.containsKey(s.charAt(i))），就可以移动头指针（j =

Math.max(j, rempos.get(s.charAt(i)))），缩小窗口。

当输入 s = "abcabcbb" 时，我们按照滑动窗口的方法来模拟题解过程：

1. 初始化：建立一个哈希表 rempos 来记录字符最近出现的位置，初始化最长子串长度

res = 0，以及两个指针 i = 0（尾指针）和 j = 0（头指针）。

2. 开始遍历字符串 **s**：

– i = 0，字符为 'a'：

• rempos 中没有 'a'，将 'a' 添加到 rempos（'a': 1），res = max(res, i

- j + 1) = max(0, 0 - 0 + 1) = 1。

• 此时子串为 a，长度为 1。

– i = 1，字符为 'b'：

• rempos 中没有 'b'，将 'b' 添加到 rempos（'b': 2），res = max(1, 1 -

0 + 1) = 2。

• 此时子串为 ab，长度为 2。

– i = 2，字符为 'c'：

• rempos 中没有 'c'，将 'c' 添加到 rempos（'c': 3），res = max(2, 2 -

0 + 1) = 3。

• 此时子串为 abc，长度为 3。

– i = 3，字符为 'a'：

• rempos 中有 'a'，它的位置是 1。将 j 更新为 max(j, rempos.get('a'))

= max(0, 1) = 1。

• 此时子串为 bca，长度为 3。

• 更新 rempos 中 'a' 的位置为 4。

• res = max(3, 3 - 1 + 1) = 3。

– i = 4，字符为 'b'：

• rempos 中有 'b'，它的位置是 2。将 j 更新为 max(j, rempos.get('b'))

= max(1, 2) = 2。

• 此时子串为 cab，长度为 3。

• 更新 rempos 中 'b' 的位置为 5。

• res = max(3, 4 - 2 + 1) = 3。

– i = 5，字符为 'c'：

• rempos 中有 'c'，它的位置是 3。将 j 更新为 max(j, rempos.get('c'))

= max(2, 3) = 3。

• 此时子串为 abc，长度为 3。

• 更新 rempos 中 'c' 的位置为 6。

• res = max(3, 5 - 3 + 1) = 3。

– i = 6，字符为 'b'：

• rempos 中有 'b'，它的位置是 5。将 j 更新为 max(j, rempos.get('b'))

= max(3, 5) = 5。

• 此时子串为 cb，长度为 2。

 • 此处不更新 res。

• 更新 rempos 中 'b' 的位置为 7。

• res = max(3, 6 - 5 + 1) = 2。

– i = 7，字符为 'b'：

• 再次遇到 'b'，rempos 中有 'b'，它的位置是 7。将 j 更新为 max(j,

rempos.get('b')) = max(5, 7) = 7。

• 此时子串为 b，长度为 1。

• 此处不更新 res。

• 更新 rempos 中 'b' 的位置为 8。

3. 遍历结束：字符串遍历完成。

4. 输出结果：最长无重复字符子串的长度为 res = 3。

如果还是不明白的话，可以通过 ACM 的模式调试一下，一步一步跟着代码走，就明白

了。

public class Main00301 {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("输入字符串: ");

String s = scanner.nextLine(); // 从标准输入读取字符串

int length = lengthOfLongestSubstring(s); // 调用解题函数

System.out.println("没有重复的最长子串为: " + length); // 输出结果

}

public static int lengthOfLongestSubstring(String s) {

HashMap<Character, Integer> rempos = new HashMap<>();

int res = 0;

for (int i = 0, j = 0; i < s.length(); i++) {

System.out.println("i: " + i + ", j: " + j);

if (rempos.containsKey(s.charAt(i))) {

j = Math.max(j, rempos.get(s.charAt(i)));

}

// 把子串也打印出来

System.out.println("sub: " + s.substring(j, i + 1));

res = Math.max(res, i - j + 1);

rempos.put(s.charAt(i), i + 1);

}

return res;

}

}

在这个过程中，滑动窗口从每个可能的起始位置开始，尽可能地向右扩展。每当遇到重复

字符时，窗口的左边界就会向右移动，以保证窗口内没有重复字符。通过这种方式，我们

能够找出最长的无重复字符子串。

003.%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E

6%9C%80%E9%95%BF%E5%AD%90%E4%B8%B2-20231212172800.png

时间复杂度：$ O(n) $

因为每个元素尾指针只访问过一遍，头指针依靠尾指针访问过的信息进行移动，所以时间

复杂度比之前的暴力方法低了一个次方级别。

总结

本次我们用了新的算法：滑动窗口（可以戳视频链接再加深一下印象），一次遍历，通过

移动头指针和尾指针来找出一个区间，相对于暴力的两次遍历，显然时间复杂度大大降低

了。

这次的题解涉及到的知识点相对较多，但题解中都给出了对应的学习资料，相信大家看完

后都能串联到一起，形成一个完整的知识体系。

其中的字符串可以参考下面这个链接：

• 字符串

涉及到一个两个数中求最大的数学操作类 Math 我这里简单帮大家总结一下：

• Math.abs(x)：返回 x 的绝对值。

• Math.ceil(x)：返回大于或等于 x 的最小整数。

• Math.floor(x)：返回小于或等于 x 的最大整数。

• Math.round(x)：将 x 四舍五入为最接近的整数。

• Math.max(x, y)：返回 x 和 y 中的较大值。

• Math.min(x, y)：返回 x 和 y 中的较小值。

• Math.pow(x, y)：返回 x 的 y 次方。

• Math.sqrt(x)：返回 x 的平方根。

• Math.sin(x)：返回 x 的正弦值。

• Math.cos(x)：返回 x 的余弦值。

• Math.tan(x)：返回 x 的正切值。

• Math.random()：返回一个大于等于 0 且小于 1 的随机浮点数。

力扣链接：https://leetcode.cn/problems/longest-substring-without-repeating-

characters/