本题采用滑动窗口双指针算法解决“无重复字符的最长子串”问题。其核心本质是通过右指针无条件向右扩展以引入新字符并利用固定大小的频次数组在常数时间内检测字符冲突进而驱动左指针向右收缩以解除重复状态。当前提供的源码实现了线性时间内的动态单次扫描最终走向是通过实时计算并比较合法窗口的区间跨度来直接锁定最大子串长度。一、 问题本质与数据模型对于给定的字符串 s设其长度为 n。任意连续子串可以定义为一个闭区间 [left, right]其中 0 left right n。该问题的核心约束条件为区间 [left, right] 内的所有字符其在当前窗口内的出现频次必须全部等于 1。算法的目标是在全文本遍历中最大化该区间的跨度即最大化以下数值区间长度 right - left 1为了在 O(1) 阶常数时间内判定新移入的字符是否导致重复算法引入了一个容量为 128 的整型数组 win 作为哈希映射表对应 ASCII 码表。该数组利用字符的 ASCII 码值作为索引实时存储并更新当前窗口内各个字符的出现次数。二、 算法演进对比在解决该线性区间去重问题时滑动窗口法在时间与空间的资源利用率上达到了最优平衡解法名称时间复杂度空间复杂度核心原理物理瓶颈暴力枚举法O(n^2)O(min(n, m))枚举所有可能的子串起点与终点并使用集合独立去重存在大量重复的字符扫描时间开销随字符串长度呈平方级增长滑动窗口频次数组版O(n)O(m) 其中 m128通过双指针同向移动维护区间利用 ASCII 数组常数级更新状态左指针需要逐位移动以消除冲突字符最坏情况下每个字符被访问两次滑动窗口索引映射版O(n)O(m) 其中 m128数组直接存储字符上一次出现的索引位置冲突时左指针实现跳跃式移动逻辑判断分支增加需要处理历史索引在当前窗口左侧的无效情况三、 滑动窗口核心逻辑拆解该算法的运行机制完全依赖于右指针的无条件前推和左指针的有条件收缩1. 变量定义与职责划分left: 滑动窗口的左边界指针用于在发生字符重复时向右收缩区间以消除冲突。right: 滑动窗口的右边界指针作为主循环变量逐位向右扩展以遍历整个字符串。win: 一个大小固定为 128 的整型数组通过字符对应的 ASCII 码作为下标记录当前窗口区间内每个字符的出现频次。ans: 记录遍历全过程中所产生过的最大合法窗口长度。2. 冲突触发与消除机制窗口扩大每轮循环中右指针指向的新字符c s.charAt(right)进入窗口对应的频次计数器执行win[c]。冲突判定与收缩如果执行后满足win[c] 1说明当前字符c在之前的[left, right-1]区间内已经存在当前窗口进入非法重复状态。此时触发while循环左指针指向的字符d s.charAt(left)被移出窗口执行win[d]--随后left。该收缩过程持续执行直到此前重复的那个字符被完全排除在窗口之外使得win[c]恢复为 1。长度更新当执行流退出while循环时意味着窗口重新恢复为“无重复字符”的合法状态。此时计算当前合法窗口的大小right - left 1并与历史最大值ans进行取大比较并完成更新。四、 算法执行状态机步进示例以输入数据s pwwkew为例核心变量在运行过程中的演进状态如下表所示步骤指针状态当前字符 c频次数组变化窗口合法性与收缩逻辑最大长度 ans初始化left0, right0-所有 ASCII 下标对应值均为 0初始合法ans 0第 1 步left0, right0pwin[p] 1合法跳过 while 循环当前窗口 pmax(0, 0-01) 1第 2 步left0, right1wwin[w] 1合法跳过 while 循环当前窗口 pwmax(1, 1-01) 2第 3 步left0, right2wwin[w] 2不合法(win[w] 1)1. 移出 p: win[p]0, left12. 移出 w: win[w]1, left2退出 while当前窗口 wmax(2, 2-21) 2第 4 步left2, right3kwin[k] 1合法跳过 while 循环当前窗口 wkmax(2, 3-21) 2第 5 步left2, right4ewin[e] 1合法跳过 while 循环当前窗口 wkemax(2, 4-21) 3第 6 步left2, right5wwin[w] 2不合法(win[w] 1)1. 移出 w: win[w]1, left3退出 while当前窗口 kewmax(3, 5-31) 3五、 Java 源码实现含标准注释Javaclass Solution { public int lengthOfLongestSubstring(String s) { // 初始化左指针 int left 0; // 建立大小为128的频次数组覆盖所有标准的ASCII字符 int[] win new int[128]; // 记录最大长度结果 int ans 0; // 右指针开始向右遍历字符串 for (int right 0; right s.length(); right) { char c s.charAt(right); // 新字符进入窗口频次自增 win[c]; // 当新进入的字符频次大于1时说明窗口内出现重复字符 while (win[c] 1) { // 左指针指向的字符移出窗口频次自减 char d s.charAt(left); win[d]--; // 左指针右移收缩窗口 left; } // 此时窗口必然恢复合法状态计算当前窗口长度并更新全局最大值 ans Math.max(ans, right - left 1); } return ans; } }六、 复杂度分析1. 时间复杂度O(n)原因虽然代码内部嵌套了一个while循环但从宏观来看right指针在for循环中从 0 移动到 n-1执行了 n 次。而left指针在整个算法生命周期内只在while循环内部执行自增操作其移动轨迹同样是从 0 开始最多移动到 n-1。结论字符串中的每一个字符最多被right指针访问一次被left指针访问一次。总体的基本操作执行次数不超过 2n 次因此时间复杂度稳定在 O(n)其中 n 为字符串s的长度。2. 空间复杂度O(1)原因算法中申请的辅助存储空间为一个固定大小的整型数组win[128]以及常数个整型变量left,right,ans。结论该频次数组的长度由字符集的大小ASCII 码的范围决定与输入字符串s的实际长度 n 无任何线性关联空间消耗在全局运行中保持为常数阶 O(1)。