003.无重复字符的最长子串
作者：沉默王二 发布时间：2023-12-12T17:50:45.698+0800
之前星球还没有 Markdown 的功能， 所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：
- 增加代码注释，这样大家更容易看懂并掌握题解；
- 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
- 增加手绘图，这样大家更容易理解解题思路；
- 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
- 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
- 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
- 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
并且增加了技术派专栏的阅读地址，只需要绑定星球编号就可以通过「微信扫码登录」的方式在技术派网站上阅读，这样大家的阅读选择也会更加多样化（语雀、技术派、星球都可以，喜欢哪个用哪个）。
- 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
- 技术派专栏地址：https://paicoding.com/column/7/3
- 星球原地址：https://t.zsxq.com/15PCRWOYj
我知道，市面上已经有不少的刷题笔记了，二哥也看过很多，但讲真，有些还是看不太懂，可能是因为天赋不够，也可能是因为这些刷题笔记一开始是针对 C语言、Python、Go 或者 C++ 的，后来才翻译成 Java 语言，就导致阅读起来并不幸福🥰。
那我希望《二哥的 LeetCode 刷题笔记》能够给学习算法的球友提供一些不一样的刷题思路，从我自己的角度出发，题解可能会更容易掌握，当然了，最重要的还是教给大家举一反三的解题能力。
这对于那些打算冲中大厂的球友来说，至关重要，因为中大厂几乎都会有算法的笔试题，然后才会有面试机会。当然了，对于那些想通过刷题来学习 Java 的球友，无疑也会多一种选择，冲。
在这里，必须要感谢球友 @炳源，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！
《二哥的 LeetCode 刷题笔记》真的经典。
------------------------by鲁迅
题意
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例
输入:s="abcabcbb"
解释:因为无重复字符的最长子串是"abc"，所以其长度为3。
难度
中等
分析1
看完这道题目的描述，脑袋里面要先搞清楚几个概念：
- 什么是子串？
- 什么是最长子串？
- 什么是不含重复字符的最长子串？
这三个概念搞清楚，才能去写题解，对吧？
什么是子串？拿题目给出的示例来说，abcabcbb，它的子串有：
a、b、c、a、b、c、b、b这种单个子串
abc、bca、cab、bcb、cbb这种三个字符组成的子串abca、bcab、cabc、abcb这种四个字符组成的子串abcab、bcabc、cabcb、abcbb这种五个字符组成的子串abcabc、bcabcb、cabcbb这种六个字符组成的子串abcabcbbcabcbb这种七个字符组成的子串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 {
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" 时，我们用该题解来模拟一下整个题解的过程。
- 初始化：最长子串长度 res = 0。
- 开始外层循环：逐字符遍历字符串 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 遍历完整个字符串。
- 结束遍历：所有字符都已被检查。
- 返回结果：最长无重复字符子串的长度 res。在这个例子中，最长的无重复字符子串长度为 3。
对 for 循环或者 break 比较陌生的球友，可以通过 ACM 的模式在 Intellij IDEA 中 debug 以下，瞬间就明白了。
public class Main003 {
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; }}
好，虽然通过两层循环也能解出来，但是这种暴力解法的时间复杂度是 ，效率不高，我们需要想办法优化一下。
分析 2
接下来，我们介绍一个在Java中被隐藏起来的概念——指针，在C/C++中，指针是一种特殊的变量类型，用来记录变量的值在内存中的位置。
在数据结构中，也有一个指针的概念，但它和C/C++中的指针不太一样，虽然它也指向一个的位置，但并非指向存储值的物理位置，而是指向其在数据结构中的相对位置，就如同 Java 中熟知的下标（索引）一样，我们来看一段熟悉的代码：
for(inti=1;i
上面的代码中，i其实就是一个指针，被我们用来表示数组 a 中 1到n 的位置，实际上这就是数据结构中指针的概念。
再来看这段代码，在二分查找中：
int lef = 1, rig = n;
int mid = (lef + rig) / 2; // 计算中间位置 if(a[mid] < goalVal) lef = mid; // 如果中间位置的值小于目标值，调整左边界 else rig = mid; // 如果中间位置的值大于或等于目标值，调整右边界}
这里面的lef,rig,mid其实都是指针，指向数组中的某个位置，然后再用a[]（a是一个数组）来取出这个位置的元素进行判断。
我们再来横向比较一下引用、指针、下标这些容易混淆的概念：
明白这一点，我们再来讲一个算法中经常出现的概念——滑动窗口。
题目要我们求解的是一个区间，所以我们可以考虑这样两个指针，一个指向这个区间的开头，另外一个则指向这个区间的结尾。
我们让头指针不动，向后扩展尾指针，直到遇见重复元素（见下图）：
图片出自**[LeetCode 的一个作者 Ikaruga](https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/228576/longest-substring-without-repeating-characters-b-2/)**
否则，向后移动头指针，重复之前的动作。
一个位置一个位置移动，也太低效了，有没有更好的办法呢？
我们可以用一个 **[HashMap](https://javabetter.cn/collection/hashmap.html)** 来存储每个字符的位置，这样我们就可以直接跳到这个字符上次出现的位置，而不用一个一个地移动头指针了。
那由头指针和尾指针组成的区间，我们称之为**滑动窗口**。我用图简单来画一下大家就明白了。
学过计算机网络的同学，应该都知道滑动窗口协议，用于网络数据传输时的流量控制，以避免网络拥塞。算法中的滑动窗口主要用来解决数组/字符串的子元素问题，比如今天这道题目，在字符串中寻找最长不含重复字符的子串。
图片来自博客园的huansky
推荐阅读资料：**[博客园上这篇关于滑动窗口的帖子写的非常不错](https://www.cnblogs.com/huansky/p/13488234.html)**
我们来看一下滑动窗口的题解：
class Solution {
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; // 返回最长子串的长度 }}
滑动窗口方法只需要一次遍历：
- 使用两个指针（通常称为头指针和尾指针）创建一个动态的窗口。这个窗口代表当前考虑的子串。
- 移动尾指针：逐个检查字符，扩展窗口。
- 移动头指针：一旦遇到重复字符，就移动头指针，缩小窗口直到子串中不再包含重复字符。
使用 **[HashMap](https://javabetter.cn/collection/hashmap.html)** 记录每个字符最近一次出现的位置（[rempos.put](http://rempos.put)(s.charAt(i), i + 1)）。一旦出现重复字符（rempos.containsKey(s.charAt(i))），就可以移动头指针（j = [Math.max](http://Math.max)(j, [rempos.get](http://rempos.get)(s.charAt(i)))），缩小窗口。
当输入 s = "abcabcbb" 时，我们按照滑动窗口的方法来模拟题解过程：
- **初始化**：建立一个哈希表 rempos 来记录字符最近出现的位置，初始化最长子串长度 res = 0，以及两个指针 i = 0（尾指针）和 j = 0（头指针）。
- **开始遍历字符串 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](http://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](http://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](http://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](http://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](http://rempos.get)('b')) = max(5, 7) = 7。
- 此时子串为b，长度为 1。
- 此处不更新 res。
- 更新 rempos 中 'b' 的位置为 8。
- **遍历结束**：字符串遍历完成。
- **输出结果**：最长无重复字符子串的长度为 res = 3。
如果还是不明白的话，可以通过 ACM 的模式调试一下，一步一步跟着代码走，就明白了。
public class Main00301 {
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; }}
在这个过程中，滑动窗口从每个可能的起始位置开始，尽可能地向右扩展。每当遇到重复字符时，窗口的左边界就会向右移动，以保证窗口内没有重复字符。通过这种方式，我们能够找出最长的无重复字符子串。
时间复杂度：
因为每个元素尾指针只访问过一遍，头指针依靠尾指针访问过的信息进行移动，所以时间复杂度比之前的暴力方法低了一个次方级别。
### **总结**
本次我们用了新的算法：**[滑动窗口](https://www.bilibili.com/video/BV14Q4y1P7Np/)**（可以戳视频链接再加深一下印象），一次遍历，通过移动头指针和尾指针来找出一个区间，相对于暴力的两次遍历，显然时间复杂度大大降低了。
这次的题解涉及到的知识点相对较多，但题解中都给出了对应的学习资料，相信大家看完后都能串联到一起，形成一个完整的知识体系。
其中的字符串可以参考下面这个链接：
- **[字符串](https://javabetter.cn/string/string-source.html)**
涉及到一个两个数中求最大的数学操作类 Math 我这里简单帮大家总结一下：
- [Math.abs](http://Math.abs)(x)：返回x的绝对值。
- [Math.ceil](http://Math.ceil)(x)：返回大于或等于x的最小整数。
- [Math.floor](http://Math.floor)(x)：返回小于或等于x的最大整数。
- [Math.round](http://Math.round)(x)：将x四舍五入为最接近的整数。
- [Math.max](http://Math.max)(x, y)：返回x和y中的较大值。
- [Math.min](http://Math.min)(x, y)：返回x和y中的较小值。
- [Math.pow](http://Math.pow)(x, y)：返回x的y次方。
- [Math.sqrt](http://Math.sqrt)(x)：返回x的平方根。
- [Math.sin](http://Math.sin)(x)：返回x的正弦值。
- [Math.cos](http://Math.cos)(x)：返回x的余弦值。
- [Math.tan](http://Math.tan)(x)：返回x的正切值。
- [Math.random](http://Math.random)()：返回一个大于等于0且小于1的随机浮点数。
力扣链接：**[https://leetcode.cn/problems/longest-substring-without-repeating-characters/](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)**
### **一步一个脚印**
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
之前星球还没有 Markdown 的功能， 所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：
- 增加代码注释，这样大家更容易看懂并掌握题解；
- 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
- 增加手绘图，这样大家更容易理解解题思路；
- 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
- 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
- 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
- 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
并且增加了技术派专栏的阅读地址，只需要绑定**星球编号**就可以通过「**微信扫码登录**」的方式在技术派网站上阅读，这样大家的阅读选择也会更加多样化（语雀、技术派、星球都可以，喜欢哪个用哪个）。
- 语雀专栏地址+密码可通过星球置顶帖查看：[https://t.zsxq.com/15rEo9Pdu](https://t.zsxq.com/15rEo9Pdu)
- 技术派专栏地址：[https://paicoding.com/column/7/3](https://paicoding.com/column/7/3)
- 星球原地址：[https://t.zsxq.com/15PCRWOYj](https://t.zsxq.com/15PCRWOYj)
我知道，市面上已经有不少的刷题笔记了，二哥也看过很多，但讲真，有些还是看不太懂，可能是因为天赋不够，也可能是因为这些刷题笔记一开始是针对 C语言、Python、Go 或者 C++ 的，后来才翻译成 Java 语言，就导致阅读起来并不幸福🥰。
那我希望《**二哥的 LeetCode 刷题笔记**》能够给学习算法的球友提供一些不一样的刷题思路，从我自己的角度出发，题解可能会更容易掌握，当然了，最重要的还是教给大家举一反三的解题能力。
这对于那些打算冲中大厂的球友来说，至关重要，因为中大厂几乎都会有算法的笔试题，然后才会有面试机会。当然了，对于那些想通过刷题来学习 Java 的球友，无疑也会多一种选择，冲。
在这里，必须要感谢球友 **@炳源**，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！
《二哥的 LeetCode 刷题笔记》真的经典。
------------------------by鲁迅
### **题意**
给定一个字符串 s ，请你找出其中不含有重复字符的 **最长子串** 的长度。
### **示例**
输入:s="abcabcbb"
解释:因为无重复字符的最长子串是"abc"，所以其长度为3。
### **难度**
中等
### **分析1**
看完这道题目的描述，脑袋里面要先搞清楚几个概念：
- 什么是子串？
- 什么是最长子串？
- 什么是不含重复字符的最长子串？
这三个概念搞清楚，才能去写题解，对吧？
什么是子串？拿题目给出的示例来说，abcabcbb，它的子串有：
a、b、c、a、b、c、b、b这种单个子串
abc、bca、cab、bcb、cbb这种三个字符组成的子串abca、bcab、cabc、abcb这种四个字符组成的子串abcab、bcabc、cabcb、abcbb这种五个字符组成的子串abcabc、bcabcb、cabcbb这种六个字符组成的子串abcabcbbcabcbb这种七个字符组成的子串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 {
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 码字符集](https://javabetter.cn/basic-extra-meal/java-unicode.html#_1-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" 时，我们用该题解来模拟一下整个题解的过程。
- **初始化**：最长子串长度 res = 0。
- **开始外层循环**：逐字符遍历字符串 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 遍历完整个字符串。
- **结束遍历**：所有字符都已被检查。
- **返回结果**：最长无重复字符子串的长度 res。在这个例子中，最长的无重复字符子串长度为 3。
对 for 循环或者 break 比较陌生的球友，可以通过 ACM 的模式在 Intellij IDEA 中 debug 以下，瞬间就明白了。
public class Main003 {
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; }}
好，虽然通过两层循环也能解出来，但是这种暴力解法的时间复杂度是 ，效率不高，我们需要想办法优化一下。
### **分析 2**
接下来，我们介绍一个在Java中被隐藏起来的概念——指针，在C/C++中，指针是一种特殊的变量类型，用来记录变量的值在内存中的位置。
在数据结构中，也有一个指针的概念，但它和C/C++中的指针不太一样，虽然它也指向一个的位置，但并非指向存储值的物理位置，而是指向其在数据结构中的相对位置，就如同 Java 中熟知的下标（索引）一样，我们来看一段熟悉的代码：
for(inti=1;i
上面的代码中，i其实就是一个指针，被我们用来表示数组 a 中 1到n 的位置，实际上这就是数据结构中指针的概念。
再来看这段代码，在二分查找中：
int lef = 1, rig = n;
int mid = (lef + rig) / 2; // 计算中间位置 if(a[mid] < goalVal) lef = mid; // 如果中间位置的值小于目标值，调整左边界 else rig = mid; // 如果中间位置的值大于或等于目标值，调整右边界}
这里面的lef,rig,mid其实都是指针，指向数组中的某个位置，然后再用a[]（a是一个数组）来取出这个位置的元素进行判断。
我们再来横向比较一下引用、指针、下标这些容易混淆的概念：
明白这一点，我们再来讲一个算法中经常出现的概念——滑动窗口。
题目要我们求解的是一个区间，所以我们可以考虑这样两个指针，一个指向这个区间的开头，另外一个则指向这个区间的结尾。
我们让头指针不动，向后扩展尾指针，直到遇见重复元素（见下图）：
图片出自**LeetCode 的一个作者 Ikaruga **
否则，向后移动头指针，重复之前的动作。
一个位置一个位置移动，也太低效了，有没有更好的办法呢？
我们可以用一个 HashMap 来存储每个字符的位置，这样我们就可以直接跳到这个字符上次出现的位置，而不用一个一个地移动头指针了。
那由头指针和尾指针组成的区间，我们称之为滑动窗口。我用图简单来画一下大家就明白了。
学过计算机网络的同学，应该都知道滑动窗口协议，用于网络数据传输时的流量控制，以避免网络拥塞。算法中的滑动窗口主要用来解决数组/字符串的子元素问题，比如今天这道题目，在字符串中寻找最长不含重复字符的子串。
图片来自博客园的huansky
推荐阅读资料：博客园上这篇关于滑动窗口的帖子写的非常不错
我们来看一下滑动窗口的题解：
class Solution {
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; // 返回最长子串的长度 }}
滑动窗口方法只需要一次遍历：
- 使用两个指针（通常称为头指针和尾指针）创建一个动态的窗口。这个窗口代表当前考虑的子串。
- 移动尾指针：逐个检查字符，扩展窗口。
- 移动头指针：一旦遇到重复字符，就移动头指针，缩小窗口直到子串中不再包含重复字符。
使用 HashMap 记录每个字符最近一次出现的位置（rempos.put (s.charAt(i), i + 1)）。一旦出现重复字符（rempos.containsKey(s.charAt(i))），就可以移动头指针（j = Math.max (j, rempos.get (s.charAt(i)))），缩小窗口。
当输入 s = "abcabcbb" 时，我们按照滑动窗口的方法来模拟题解过程：
- 初始化：建立一个哈希表 rempos 来记录字符最近出现的位置，初始化最长子串长度 res = 0，以及两个指针 i = 0（尾指针）和 j = 0（头指针）。
- 开始遍历字符串 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。
- 遍历结束：字符串遍历完成。
- 输出结果：最长无重复字符子串的长度为 res = 3。
如果还是不明白的话，可以通过 ACM 的模式调试一下，一步一步跟着代码走，就明白了。
public class Main00301 {
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; }}
在这个过程中，滑动窗口从每个可能的起始位置开始，尽可能地向右扩展。每当遇到重复字符时，窗口的左边界就会向右移动，以保证窗口内没有重复字符。通过这种方式，我们能够找出最长的无重复字符子串。
时间复杂度：
因为每个元素尾指针只访问过一遍，头指针依靠尾指针访问过的信息进行移动，所以时间复杂度比之前的暴力方法低了一个次方级别。
总结
本次我们用了新的算法：滑动窗口 （可以戳视频链接再加深一下印象），一次遍历，通过移动头指针和尾指针来找出一个区间，相对于暴力的两次遍历，显然时间复杂度大大降低了。
这次的题解涉及到的知识点相对较多，但题解中都给出了对应的学习资料，相信大家看完后都能串联到一起，形成一个完整的知识体系。
其中的字符串可以参考下面这个链接：
涉及到一个两个数中求最大的数学操作类 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/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
之前星球还没有 Markdown 的功能， 所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：
- 增加代码注释，这样大家更容易看懂并掌握题解；
- 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
- 增加手绘图，这样大家更容易理解解题思路；
- 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
- 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
- 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
- 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
并且增加了技术派专栏的阅读地址，只需要绑定星球编号就可以通过「微信扫码登录」的方式在技术派网站上阅读，这样大家的阅读选择也会更加多样化（语雀、技术派、星球都可以，喜欢哪个用哪个）。
- 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
- 技术派专栏地址：https://paicoding.com/column/7/3
- 星球原地址：https://t.zsxq.com/15PCRWOYj
我知道，市面上已经有不少的刷题笔记了，二哥也看过很多，但讲真，有些还是看不太懂，可能是因为天赋不够，也可能是因为这些刷题笔记一开始是针对 C语言、Python、Go 或者 C++ 的，后来才翻译成 Java 语言，就导致阅读起来并不幸福🥰。
那我希望《二哥的 LeetCode 刷题笔记》能够给学习算法的球友提供一些不一样的刷题思路，从我自己的角度出发，题解可能会更容易掌握，当然了，最重要的还是教给大家举一反三的解题能力。
这对于那些打算冲中大厂的球友来说，至关重要，因为中大厂几乎都会有算法的笔试题，然后才会有面试机会。当然了，对于那些想通过刷题来学习 Java 的球友，无疑也会多一种选择，冲。
在这里，必须要感谢球友 @炳源，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！
《二哥的 LeetCode 刷题笔记》真的经典。
------------------------by鲁迅
题意
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例
输入:s="abcabcbb"
解释:因为无重复字符的最长子串是"abc"，所以其长度为3。
难度
中等
分析1
看完这道题目的描述，脑袋里面要先搞清楚几个概念：
- 什么是子串？
- 什么是最长子串？
- 什么是不含重复字符的最长子串？
这三个概念搞清楚，才能去写题解，对吧？
什么是子串？拿题目给出的示例来说，abcabcbb，它的子串有：
a、b、c、a、b、c、b、b这种单个子串
abc、bca、cab、bcb、cbb这种三个字符组成的子串abca、bcab、cabc、abcb这种四个字符组成的子串abcab、bcabc、cabcb、abcbb这种五个字符组成的子串abcabc、bcabcb、cabcbb这种六个字符组成的子串abcabcbbcabcbb这种七个字符组成的子串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 {
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" 时，我们用该题解来模拟一下整个题解的过程。
- 初始化：最长子串长度 res = 0。
- 开始外层循环：逐字符遍历字符串 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 遍历完整个字符串。
- 结束遍历：所有字符都已被检查。
- 返回结果：最长无重复字符子串的长度 res。在这个例子中，最长的无重复字符子串长度为 3。
对 for 循环或者 break 比较陌生的球友，可以通过 ACM 的模式在 Intellij IDEA 中 debug 以下，瞬间就明白了。
public class Main003 {
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; }}
好，虽然通过两层循环也能解出来，但是这种暴力解法的时间复杂度是 ，效率不高，我们需要想办法优化一下。
分析 2
接下来，我们介绍一个在Java中被隐藏起来的概念——指针，在C/C++中，指针是一种特殊的变量类型，用来记录变量的值在内存中的位置。
在数据结构中，也有一个指针的概念，但它和C/C++中的指针不太一样，虽然它也指向一个的位置，但并非指向存储值的物理位置，而是指向其在数据结构中的相对位置，就如同 Java 中熟知的下标（索引）一样，我们来看一段熟悉的代码：
for(inti=1;i
上面的代码中，i其实就是一个指针，被我们用来表示数组 a 中 1到n 的位置，实际上这就是数据结构中指针的概念。
再来看这段代码，在二分查找中：
int lef = 1, rig = n;
int mid = (lef + rig) / 2; // 计算中间位置 if(a[mid] < goalVal) lef = mid; // 如果中间位置的值小于目标值，调整左边界 else rig = mid; // 如果中间位置的值大于或等于目标值，调整右边界}
这里面的lef,rig,mid其实都是指针，指向数组中的某个位置，然后再用a[]（a是一个数组）来取出这个位置的元素进行判断。
我们再来横向比较一下引用、指针、下标这些容易混淆的概念：
明白这一点，我们再来讲一个算法中经常出现的概念——滑动窗口。
题目要我们求解的是一个区间，所以我们可以考虑这样两个指针，一个指向这个区间的开头，另外一个则指向这个区间的结尾。
我们让头指针不动，向后扩展尾指针，直到遇见重复元素（见下图）：
图片出自**[LeetCode 的一个作者 Ikaruga](https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/228576/longest-substring-without-repeating-characters-b-2/)**
否则，向后移动头指针，重复之前的动作。
一个位置一个位置移动，也太低效了，有没有更好的办法呢？
我们可以用一个 **[HashMap](https://javabetter.cn/collection/hashmap.html)** 来存储每个字符的位置，这样我们就可以直接跳到这个字符上次出现的位置，而不用一个一个地移动头指针了。
那由头指针和尾指针组成的区间，我们称之为**滑动窗口**。我用图简单来画一下大家就明白了。
学过计算机网络的同学，应该都知道滑动窗口协议，用于网络数据传输时的流量控制，以避免网络拥塞。算法中的滑动窗口主要用来解决数组/字符串的子元素问题，比如今天这道题目，在字符串中寻找最长不含重复字符的子串。
图片来自博客园的huansky
推荐阅读资料：**[博客园上这篇关于滑动窗口的帖子写的非常不错](https://www.cnblogs.com/huansky/p/13488234.html)**
我们来看一下滑动窗口的题解：
class Solution {
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; // 返回最长子串的长度 }}
滑动窗口方法只需要一次遍历：
- 使用两个指针（通常称为头指针和尾指针）创建一个动态的窗口。这个窗口代表当前考虑的子串。
- 移动尾指针：逐个检查字符，扩展窗口。
- 移动头指针：一旦遇到重复字符，就移动头指针，缩小窗口直到子串中不再包含重复字符。
使用 **[HashMap](https://javabetter.cn/collection/hashmap.html)** 记录每个字符最近一次出现的位置（[rempos.put](http://rempos.put)(s.charAt(i), i + 1)）。一旦出现重复字符（rempos.containsKey(s.charAt(i))），就可以移动头指针（j = [Math.max](http://Math.max)(j, [rempos.get](http://rempos.get)(s.charAt(i)))），缩小窗口。
当输入 s = "abcabcbb" 时，我们按照滑动窗口的方法来模拟题解过程：
- **初始化**：建立一个哈希表 rempos 来记录字符最近出现的位置，初始化最长子串长度 res = 0，以及两个指针 i = 0（尾指针）和 j = 0（头指针）。
- **开始遍历字符串 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](http://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](http://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](http://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](http://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](http://rempos.get)('b')) = max(5, 7) = 7。
- 此时子串为b，长度为 1。
- 此处不更新 res。
- 更新 rempos 中 'b' 的位置为 8。
- **遍历结束**：字符串遍历完成。
- **输出结果**：最长无重复字符子串的长度为 res = 3。
如果还是不明白的话，可以通过 ACM 的模式调试一下，一步一步跟着代码走，就明白了。
public class Main00301 {
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; }}
在这个过程中，滑动窗口从每个可能的起始位置开始，尽可能地向右扩展。每当遇到重复字符时，窗口的左边界就会向右移动，以保证窗口内没有重复字符。通过这种方式，我们能够找出最长的无重复字符子串。
时间复杂度：
因为每个元素尾指针只访问过一遍，头指针依靠尾指针访问过的信息进行移动，所以时间复杂度比之前的暴力方法低了一个次方级别。
### **总结**
本次我们用了新的算法：**[滑动窗口](https://www.bilibili.com/video/BV14Q4y1P7Np/)**（可以戳视频链接再加深一下印象），一次遍历，通过移动头指针和尾指针来找出一个区间，相对于暴力的两次遍历，显然时间复杂度大大降低了。
这次的题解涉及到的知识点相对较多，但题解中都给出了对应的学习资料，相信大家看完后都能串联到一起，形成一个完整的知识体系。
其中的字符串可以参考下面这个链接：
- **[字符串](https://javabetter.cn/string/string-source.html)**
涉及到一个两个数中求最大的数学操作类 Math 我这里简单帮大家总结一下：
- [Math.abs](http://Math.abs)(x)：返回x的绝对值。
- [Math.ceil](http://Math.ceil)(x)：返回大于或等于x的最小整数。
- [Math.floor](http://Math.floor)(x)：返回小于或等于x的最大整数。
- [Math.round](http://Math.round)(x)：将x四舍五入为最接近的整数。
- [Math.max](http://Math.max)(x, y)：返回x和y中的较大值。
- [Math.min](http://Math.min)(x, y)：返回x和y中的较小值。
- [Math.pow](http://Math.pow)(x, y)：返回x的y次方。
- [Math.sqrt](http://Math.sqrt)(x)：返回x的平方根。
- [Math.sin](http://Math.sin)(x)：返回x的正弦值。
- [Math.cos](http://Math.cos)(x)：返回x的余弦值。
- [Math.tan](http://Math.tan)(x)：返回x的正切值。
- [Math.random](http://Math.random)()：返回一个大于等于0且小于1的随机浮点数。
力扣链接：**[https://leetcode.cn/problems/longest-substring-without-repeating-characters/](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)**
### **一步一个脚印**
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412