目录
编辑
一、 引言与题目描述
二、 从零开始的推理：暴力解法与瓶颈
2.1 穷举所有子串（暴力解法）
2.2 寻找瓶颈：我们重复计算了什么？
三、 为什么可以使用滑动窗口？（核心推理）
3.1 单调性的发现
3.2 算法设计
四、Java 代码
五、 算法正确性证明（严谨推理）
六、 复杂度分析
七、 进阶优化思路
一、 引言与题目描述
题目：给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
示例：
输入:
s = "abcabcbb"，输出:3（最长子串为 "abc"）输入:
s = "bbbbb"，输出:1（最长子串为 "b"）输入:
s = "pwwkew"，输出:3（最长子串为 "wke"）
提示：
0≤s.length≤10 ^ 5
s由英文字母、数字、符号和空格组成。
面对这道题，我们如何从零开始思考，并最终写出优雅的 O(N) 算法？让我们开始推理。
二、 从零开始的推理：暴力解法与瓶颈
2.1 穷举所有子串（暴力解法）
寻找“最长”，最直观的想法就是检查所有的子串。我们可以用两层for循环枚举子串的起点i和终点j，然后再用一层循环或者哈希表判断s[i...j]是否有重复字符。
时间复杂度：枚举起点和终点 O(N^2)，检查重复 O(N)，总复杂度 O(N^3)。
即使优化到 O(N^2)（一边向右扩展终点，一边用哈希表判重），对于 N=105 的数据规模，必定会超时 .
2.2 寻找瓶颈：我们重复计算了什么？
假设字符串是"abcabcbb"。
我们从第一个
a开始，向右探查，得到"abc"。下一个字符是a，出现了重复，子串失效。按照暴力解法，下一步我们会把起点移到第二个字符
b，即"bca..."，重新开始检查。
发现瓶颈：当我们发现"abca"出现重复时，我们其实已经知道"abc"是无重复的。当我们把起点往右移一步变成"bc"时，这个"bc"依然是原来"abc"的一部分，它必然是无重复的。
我们不需要把right指针退回去重新遍历，也不需要丢弃所有已经获取的信息。这就引出了单调性。
三、 为什么可以使用滑动窗口？（核心推理）
3.1 单调性的发现
假设我们有一个区间（窗口）[left, right]表示当前的子串。
如果这个窗口内的字符没有重复，我们就尝试向右移动
right，扩大窗口，看能不能找到更长的。如果移动
right后，出现了重复，说明以当前left为起点的最长子串已经被找到了。此时，为了消除重复，我们必须把left向右移动。
关键推理：
如果[left, right]中有重复字符，那么[left-1, right]或更左侧起点的区间，必然也包含这个重复字符（因为它们包含了[left, right]的范围）。
因此，left指针永远不需要向左回退。left和right都是单向向右移动的。
这种“左右指针同向移动，维护一个区间”的思想，就是滑动窗口。
3.2 算法设计
使用双指针
left和right维护一个窗口[left, right]。right主动向右扩展，将新字符加入窗口，并记录字符出现的次数（使用哈希表）。当新加入的字符在窗口内出现次数大于 1（即出现重复）时，
left开始向右收缩，把left指向的字符移出窗口，直到那个重复的字符在窗口内唯一。在每次窗口合法（无重复）时，记录当前窗口的长度
right - left + 1，并更新最大值。
四、Java 代码
以下是基于上述思路整理出的 Java 代码：
class Solution { public int lengthOfLongestSubstring(String s) { char[] str = s.toCharArray(); int n = str.length; int left = 0, right = 0, ret = 0; // 哈希表记录窗口内字符出现的频次 Map<Character, Integer> hash = new HashMap<>(); while(right < n) { char ch = str[right]; // 1. 右指针字符进入窗口，频次 +1 hash.put(ch, hash.getOrDefault(ch, 0) + 1); // 2. 如果当前字符频次 > 1，说明出现了重复字符 // 左指针开始向右移动，直到该字符频次降为 1 while(hash.get(ch) > 1) { hash.put(str[left], hash.get(str[left]) - 1); left++; } // 3. 此时窗口 [left, right] 内必然无重复，更新答案 ret = Math.max(ret, right - left + 1); // 4. 右指针继续右移 right++; } return ret; } }细节剖析：
为什么
while(hash.get(ch) > 1)里只判断ch的频次？因为进入外层循环前，窗口内都是合法的。只有新加入的ch可能打破规则。当ch的频次降为 1 时，其他字符的频次必定也都为 1（因为其他字符没变）。这里用
Map<Character, Integer>记录了频次，实际上也可以直接记录字符最后一次出现的索引，这样可以省去while循环，直接让left跳跃（见后文进阶优化）。
五、 算法正确性证明（严谨推理）
为了证明滑动窗口算法的正确性，我们使用循环不变式来进行形式化证明。
定义：设 MaxLen(right) 为以right为结尾的无重复字符的最长子串长度。最终答案即为 0≤r<n。
循环不变式：在每次外层while(right < n)循环开始时（即执行hash.put之前），窗口[left, right-1]是一个合法的（无重复字符的）窗口，且它是以right-1结尾的最长合法子串。
证明过程：
初始化：
最初left = 0, right = 0，窗口为空[0, -1]，天然满足无重复字符的条件，长度为 0，且显然是以right-1（即 -1）结尾的最长合法子串。不变式成立。保持：
假设在某次循环开始时，不变式成立，即[left, right-1]无重复且最长。
现在进入循环，把str[right]纳入窗口。情况 A：如果没有产生重复，此时
[left, right]仍然无重复。由于之前[left, right-1]是最长的，加入新字符后依然无重复，说明它是以right结尾的最长合法子串。不变式在下次循环前成立。情况 B：如果
str[right]产生了重复。为了消除重复，left必须向右移动。假设重复字符是C。我们让left不断向右移动，直到C的频次降为 1。此时[left, right]再次变为合法。
为什么这样得到的是最长的？因为如果left不再往后移，窗口就不合法；如果left越过当前的位置，我们就会丢失可能导致更长结果的有效字符组合。所以，当C频次刚变为 1 时，我们找到了以right结尾的最长合法子串。不变式保持。
终止：
当right == n时，循环终止。此时我们已经遍历了所有的right位置，ret记录了所有以每个位置结尾的最长合法子串长度中的最大值。因此ret就是整个字符串的最长无重复子串长度。证毕。
六、 复杂度分析
时间复杂度：O(N)。
虽然代码中有一个嵌套的while循环，但left和right两个指针都只向右移动。right移动 N 次，left最多也移动 N 次。因此while内部的操作总执行次数最多为 2N 次。时间复杂度为 O(N)。空间复杂度：O(1)
这里是英文字母、数字、符号和空格，最多128个 ASCII 字符。哈希表最多存储 128 个键值对，所以空间复杂度可以认为是 O(1) 常数级别。
七、 进阶优化思路
提供的代码中，使用Map记录了字符的出现次数。当发生重复时，通过while循环一步步把left挪过去。
实际上，我们可以直接让Map记录字符最后一次出现的索引。
当遇到重复字符ch时，我们不需要while循环，直接让left跳到max(left, 上一次ch出现的索引 + 1)即可。
优化后的代码：
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int left = 0, ret = 0; // 记录字符最后一次出现的索引 Map<Character, Integer> lastIndex = new HashMap<>(); for (int right = 0; right < n; right++) { char ch = s.charAt(right); if (lastIndex.containsKey(ch)) { // 如果重复，left 直接跳过上次出现的位置 left = Math.max(left, lastIndex.get(ch) + 1); } lastIndex.put(ch, right); ret = Math.max(ret, right - left + 1); } return ret; } }注：这种写法少了一层while循环，代码更精简，常数时间执行更快。
