尧图网站建设 
LeetCode-Book 剑指 Offer 48 详解最长不含重复字符的子字符串的三种解法动态规划、哈希表与双指针【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文基于 LeetCode-Book 仓库中《剑指 Offer 48. 最长不含重复字符的子字符串》一文的完整解析系统讲解该题从暴力法到动态规划再到双指针的优化路径覆盖状态定义、转移方程的三种情况、空间复杂度优化以及动态规划 哈希表、动态规划 线性遍历、双指针 哈希表三种解法在 Python、Java、C 下的可运行实现。读完本篇你能掌握“以某位置结尾的最长子串”这一动态规划建模范式并理解如何用哈希表把查找最近重复字符的开销降到 O(1)。一、为什么暴力法不够快题目要求返回字符串s中不含重复字符的最长子串的长度。先看暴力法的复杂度下界长度为 $N$ 的字符串共有 $\frac{(1 N)N}{2}$ 个子字符串枚举全部子串需要 $O(N^2)$判断长度为 $N$ 的子串是否含重复字符需要 $O(N)$因此暴力法总复杂度为 $O(N^3)$在长字符串上不可接受。本题的关键洞察是“不含重复字符的子串”天然具有前缀闭合性——一旦区间内出现重复所有包含该区间的更长子串也都非法。这为动态规划与滑动窗口两种思路提供了基础。二、动态规划建模状态定义与转移方程状态定义设动态规划列表 $dp$$dp[j]$ 代表以字符 $s[j]$ 为结尾的“最长不重复子字符串”的长度。注意状态刻画的是“以某位置结尾”的最优长度而非全局最优这是本题 DP 能够滚动优化的前提。转移方程固定右边界 $j$设字符 $s[j]$ 左边距离最近的相同字符为 $s[i]$即 $s[i] s[j]$。分三种情况讨论当 $i 0$即 $s[j]$ 左边无相同字符则 $dp[j] dp[j-1] 1$当 $dp[j - 1] j - i$说明字符 $s[i]$ 在子字符串 $dp[j-1]$区间之外则 $dp[j] dp[j - 1] 1$当 $dp[j - 1] \geq j - i$说明字符 $s[i]$ 在子字符串 $dp[j-1]$区间之中则 $dp[j]$ 的左边界由 $s[i]$ 决定即 $dp[j] j - i$。当 $i 0$ 时由于 $dp[j - 1] \leq j$ 恒成立因而 $dp[j - 1] j - i$ 恒成立因此分支 1 和分支 2 可被合并。合并后的转移方程为$$ dp[j] \begin{cases} dp[j - 1] 1 , dp[j-1] j - i \ j - i , dp[j-1] \geq j - i \end{cases} $$返回值为 $\max(dp)$即全局的“最长不重复子字符串”的长度。空间复杂度降低由于返回值是取 $dp$ 列表最大值因此可借助变量tmp存储 $dp[j]$变量res每轮更新最大值即可。此优化可节省 $dp$ 列表使用的 $O(N)$ 大小的额外空间——后文三种解法的所有代码均体现了这一滚动优化。观察转移方程可知本质问题变为每轮遍历字符 $s[j]$ 时如何计算索引 $i$即 $s[j]$ 左边最近的相同字符位置这决定了三种解法的差异。三、方法一动态规划 哈希表O(N) 时间哈希表统计遍历字符串 $s$ 时使用哈希表记为 $dic$统计各字符最后一次出现的索引位置。左边界 $i$ 获取方式遍历到 $s[j]$ 时可通过访问哈希表 $dic[s[j]]$ 获取最近的相同字符的索引 $i$。复杂度分析时间复杂度 $O(N)$其中 $N$ 为字符串长度动态规划需遍历计算 $dp$ 列表空间复杂度 $O(1)$字符的 ASCII 码范围为 $0 \sim 127$哈希表 $dic$ 最多使用 $O(128) O(1)$ 大小的额外空间。这里有一个细节值得注意Python 的get(key, default)方法和 Java 的getOrDefault(key, default)代表当哈希表包含键key时返回对应value不包含时返回默认值default默认值取-1恰好表示“左边无相同字符”。而 C 的unordered_map没有这类便捷接口需要先用find判断键是否存在。代码Pythonclass Solution: def lengthOfLongestSubstring(self, s: str) - int: dic {} res tmp 0 for j in range(len(s)): i dic.get(s[j], -1) # 获取索引 i dic[s[j]] j # 更新哈希表 tmp tmp 1 if tmp j - i else j - i # dp[j - 1] - dp[j] res max(res, tmp) # max(dp[j - 1], dp[j]) return resJavaclass Solution { public int lengthOfLongestSubstring(String s) { MapCharacter, Integer dic new HashMap(); int res 0, tmp 0, len s.length(); for(int j 0; j len; j) { int i dic.getOrDefault(s.charAt(j), -1); // 获取索引 i dic.put(s.charAt(j), j); // 更新哈希表 tmp tmp j - i ? tmp 1 : j - i; // dp[j - 1] - dp[j] res Math.max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } }Cclass Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapchar, int dic; int res 0, tmp 0, len s.size(), i; for(int j 0; j len; j) { if(dic.find(s[j]) dic.end()) i - 1; else i dic.find(s[j])-second; // 获取索引 i dic[s[j]] j; // 更新哈希表 tmp tmp j - i ? tmp 1 : j - i; // dp[j - 1] - dp[j] res max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } };仓库中的对应源文件含测试用例与驱动代码Pythonsfo_48_the_longest_substring_without_repeated_characters_s1.pyJavasfo_48_the_longest_substring_without_repeated_characters_s1.javaCsfo_48_the_longest_substring_without_repeated_characters_s1.cpp四、方法二动态规划 线性遍历O(N²) 时间与方法一相同差异只在左边界 $i$ 的获取方式遍历到 $s[j]$ 时初始化索引 $i j - 1$向左线性遍历搜索第一个满足 $s[i] s[j]$ 的字符即可。复杂度分析时间复杂度 $O(N^2)$其中 $N$ 为字符串长度动态规划需遍历计算 $dp$ 列表占用 $O(N)$每轮计算 $dp[j]$ 时搜索 $i$ 需要遍历 $j$ 个字符占用 $O(N)$。空间复杂度 $O(1)$几个变量使用常数大小的额外空间。代码Pythonclass Solution: def lengthOfLongestSubstring(self, s: str) - int: res tmp i 0 for j in range(len(s)): i j - 1 while i 0 and s[i] ! s[j]: i - 1 # 线性查找 i tmp tmp 1 if tmp j - i else j - i # dp[j - 1] - dp[j] res max(res, tmp) # max(dp[j - 1], dp[j]) return resJavaclass Solution { public int lengthOfLongestSubstring(String s) { int res 0, tmp 0, len s.length(); for(int j 0; j len; j) { int i j - 1; while(i 0 s.charAt(i) ! s.charAt(j)) i--; // 线性查找 i tmp tmp j - i ? tmp 1 : j - i; // dp[j - 1] - dp[j] res Math.max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } }Cclass Solution { public: int lengthOfLongestSubstring(string s) { int res 0, tmp 0, len s.size(); for(int j 0; j len; j) { int i j - 1; while(i 0 s[i] ! s[j]) i--; // 线性查找 i tmp tmp j - i ? tmp 1 : j - i; // dp[j - 1] - dp[j] res max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } };仓库中的对应源文件Pythonsfo_48_the_longest_substring_without_repeated_characters_s2.pyJavasfo_48_the_longest_substring_without_repeated_characters_s2.javaCsfo_48_the_longest_substring_without_repeated_characters_s2.cpp五、方法三双指针 哈希表O(N) 时间与方法一本质等价不同点在于左边界 $i$ 的定义不同。哈希表 $dic$ 统计指针 $j$ 遍历字符 $s$哈希表统计字符 $s[j]$最后一次出现的索引。更新左指针 $i$根据上轮左指针 $i$ 和 $dic[s[j]]$每轮更新左边界 $i$保证区间 $[i 1, j]$ 内无重复字符且最大$$ i \max(dic[s[j]], i) $$更新结果 $res$取上轮 $res$ 和本轮双指针区间 $[i 1, j]$ 的宽度即 $j - i$中的最大值$$ res \max(res, j - i) $$与方法一的 DP 视角对照理解方法一维护的是“以 $j$ 结尾的最长长度tmp”方法三维护的是“合法窗口的左边界 $i$”两者每轮都在做同一件事——把窗口收缩到不含重复字符的最小合法范围再向外扩展。复杂度分析时间复杂度 $O(N)$双指针各遍历字符串一遍每轮哈希表操作为 $O(1)$。空间复杂度 $O(1)$字符的 ASCII 码范围为 $0 \sim 127$哈希表 $dic$ 最多使用 $O(128) O(1)$ 大小的额外空间。代码Pythonclass Solution: def lengthOfLongestSubstring(self, s: str) - int: dic, res, i {}, 0, -1 for j in range(len(s)): if s[j] in dic: i max(dic[s[j]], i) # 更新左指针 i dic[s[j]] j # 哈希表记录 res max(res, j - i) # 更新结果 return resJavaclass Solution { public int lengthOfLongestSubstring(String s) { MapCharacter, Integer dic new HashMap(); int i -1, res 0, len s.length(); for(int j 0; j len; j) { if(dic.containsKey(s.charAt(j))) i Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i dic.put(s.charAt(j), j); // 哈希表记录 res Math.max(res, j - i); // 更新结果 } return res; } }Cclass Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapchar, int dic; int i -1, res 0, len s.size(); for(int j 0; j len; j) { if(dic.find(s[j]) ! dic.end()) i max(i, dic.find(s[j])-second); // 更新左指针 dic[s[j]] j; // 哈希表记录 res max(res, j - i); // 更新结果 } return res; } };仓库中的对应源文件Pythonsfo_48_the_longest_substring_without_repeated_characters_s3.pyJavasfo_48_the_longest_substring_without_repeated_characters_s3.javaCsfo_48_the_longest_substring_without_repeated_characters_s3.cpp六、三种解法对比与仓库中如何运行验证复杂度总览解法时间复杂度空间复杂度核心机制暴力枚举$O(N^3)$$O(N)$判重枚举全部子串并逐一判重方法一DP 哈希表$O(N)$$O(1)$哈希表 O(1) 定位最近重复字符 $i$方法二DP 线性遍历$O(N^2)$$O(1)$每轮从 $j-1$ 向左线性搜索 $i$方法三双指针 哈希表$O(N)$$O(1)$维护无重复窗口 $[i1, j]$$i \max(dic[s[j]], i)$从源码结构看方法一与方法三的代码骨架几乎一致一个哈希表 一个整型滚动量 一次外层遍历只是滚动量的语义不同tmp是“以 $j$ 结尾的最长无重复子串长度”i是“当前合法窗口的左边界”。这也印证了原文档的结论两者本质等价方法三只是把 DP 状态“重新参数化”成了窗口左指针。仓库内的验证方式仓库对每个解法都提供了独立的、可单独运行的完整文件解法代码 测试用例 驱动代码三段落均以注释分隔测试用例统一为s abcabcbb该用例中不含重复字符的最长子串为abc三个解法均输出3。各语言目录下共 9 个文件3 种解法 × 3 种语言文件命名规则为sfo_48_the_longest_substring_without_repeated_characters_s{1,2,3}分别对应方法一、方法二、方法三。三种语言的运行环境约定从源码结构看Python每个.py文件顶部from include import *公共依赖链表、二叉树、打印工具位于 sword_for_offer/codes/python/include 目录直接python sfo_48_..._s1.py即可看到输出Java每个解法文件自带main方法并声明独立package公共类位于 sword_for_offer/codes/java/include 目录ListNode.java、TreeNode.java、PrintUtil.javaC每个解法文件自带main函数公共头文件为 include.hpp源文件通过#include ../include/include.hpp引用。小结本题是“以某位置结尾的最长子串”这一 DP 范式的典型题状态定义、三分支转移方程、取最大值得答案滚动变量tmp/res把空间从 $O(N)$ 降到 $O(1)$三种解法的差异只在于“如何找到 $s[j]$ 左边最近相同字符的索引 $i$”哈希表查询是 $O(1)$线性向左扫描是 $O(N)$双指针写法与 DP 写法本质等价面试中可根据表达习惯任选其一但需要能说明左边界更新的两个不变式区间内无重复、区间尽可能宽。同一题在 LeetCode 中对应“3. 无重复字符的最长子串”仓库在selected_coding_interview目录下也收录了它的多语言解法如 lc_3_longest_substring_without_repeating_characters_s1.py可与本文对照阅读。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 剑指 Offer 48 详解：最长不含重复字符的子字符串的三种解法（动态规划、哈希表与双指针）
LeetCode-Book 剑指 Offer 48 详解最长不含重复字符的子字符串的三种解法动态规划、哈希表与双指针【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文基于 LeetCode-Book 仓库中《剑指 Offer 48. 最长不含重复字符的子字符串》一文的完整解析系统讲解该题从暴力法到动态规划再到双指针的优化路径覆盖状态定义、转移方程的三种情况、空间复杂度优化以及动态规划 哈希表、动态规划 线性遍历、双指针 哈希表三种解法在 Python、Java、C 下的可运行实现。读完本篇你能掌握“以某位置结尾的最长子串”这一动态规划建模范式并理解如何用哈希表把查找最近重复字符的开销降到 O(1)。一、为什么暴力法不够快题目要求返回字符串s中不含重复字符的最长子串的长度。先看暴力法的复杂度下界长度为 $N$ 的字符串共有 $\frac{(1 N)N}{2}$ 个子字符串枚举全部子串需要 $O(N^2)$判断长度为 $N$ 的子串是否含重复字符需要 $O(N)$因此暴力法总复杂度为 $O(N^3)$在长字符串上不可接受。本题的关键洞察是“不含重复字符的子串”天然具有前缀闭合性——一旦区间内出现重复所有包含该区间的更长子串也都非法。这为动态规划与滑动窗口两种思路提供了基础。二、动态规划建模状态定义与转移方程状态定义设动态规划列表 $dp$$dp[j]$ 代表以字符 $s[j]$ 为结尾的“最长不重复子字符串”的长度。注意状态刻画的是“以某位置结尾”的最优长度而非全局最优这是本题 DP 能够滚动优化的前提。转移方程固定右边界 $j$设字符 $s[j]$ 左边距离最近的相同字符为 $s[i]$即 $s[i] s[j]$。分三种情况讨论当 $i 0$即 $s[j]$ 左边无相同字符则 $dp[j] dp[j-1] 1$当 $dp[j - 1] j - i$说明字符 $s[i]$ 在子字符串 $dp[j-1]$区间之外则 $dp[j] dp[j - 1] 1$当 $dp[j - 1] \geq j - i$说明字符 $s[i]$ 在子字符串 $dp[j-1]$区间之中则 $dp[j]$ 的左边界由 $s[i]$ 决定即 $dp[j] j - i$。当 $i 0$ 时由于 $dp[j - 1] \leq j$ 恒成立因而 $dp[j - 1] j - i$ 恒成立因此分支 1 和分支 2 可被合并。合并后的转移方程为$$ dp[j] \begin{cases} dp[j - 1] 1 , dp[j-1] j - i \ j - i , dp[j-1] \geq j - i \end{cases} $$返回值为 $\max(dp)$即全局的“最长不重复子字符串”的长度。空间复杂度降低由于返回值是取 $dp$ 列表最大值因此可借助变量tmp存储 $dp[j]$变量res每轮更新最大值即可。此优化可节省 $dp$ 列表使用的 $O(N)$ 大小的额外空间——后文三种解法的所有代码均体现了这一滚动优化。观察转移方程可知本质问题变为每轮遍历字符 $s[j]$ 时如何计算索引 $i$即 $s[j]$ 左边最近的相同字符位置这决定了三种解法的差异。三、方法一动态规划 哈希表O(N) 时间哈希表统计遍历字符串 $s$ 时使用哈希表记为 $dic$统计各字符最后一次出现的索引位置。左边界 $i$ 获取方式遍历到 $s[j]$ 时可通过访问哈希表 $dic[s[j]]$ 获取最近的相同字符的索引 $i$。复杂度分析时间复杂度 $O(N)$其中 $N$ 为字符串长度动态规划需遍历计算 $dp$ 列表空间复杂度 $O(1)$字符的 ASCII 码范围为 $0 \sim 127$哈希表 $dic$ 最多使用 $O(128) O(1)$ 大小的额外空间。这里有一个细节值得注意Python 的get(key, default)方法和 Java 的getOrDefault(key, default)代表当哈希表包含键key时返回对应value不包含时返回默认值default默认值取-1恰好表示“左边无相同字符”。而 C 的unordered_map没有这类便捷接口需要先用find判断键是否存在。代码Pythonclass Solution: def lengthOfLongestSubstring(self, s: str) - int: dic {} res tmp 0 for j in range(len(s)): i dic.get(s[j], -1) # 获取索引 i dic[s[j]] j # 更新哈希表 tmp tmp 1 if tmp j - i else j - i # dp[j - 1] - dp[j] res max(res, tmp) # max(dp[j - 1], dp[j]) return resJavaclass Solution { public int lengthOfLongestSubstring(String s) { MapCharacter, Integer dic new HashMap(); int res 0, tmp 0, len s.length(); for(int j 0; j len; j) { int i dic.getOrDefault(s.charAt(j), -1); // 获取索引 i dic.put(s.charAt(j), j); // 更新哈希表 tmp tmp j - i ? tmp 1 : j - i; // dp[j - 1] - dp[j] res Math.max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } }Cclass Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapchar, int dic; int res 0, tmp 0, len s.size(), i; for(int j 0; j len; j) { if(dic.find(s[j]) dic.end()) i - 1; else i dic.find(s[j])-second; // 获取索引 i dic[s[j]] j; // 更新哈希表 tmp tmp j - i ? tmp 1 : j - i; // dp[j - 1] - dp[j] res max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } };仓库中的对应源文件含测试用例与驱动代码Pythonsfo_48_the_longest_substring_without_repeated_characters_s1.pyJavasfo_48_the_longest_substring_without_repeated_characters_s1.javaCsfo_48_the_longest_substring_without_repeated_characters_s1.cpp四、方法二动态规划 线性遍历O(N²) 时间与方法一相同差异只在左边界 $i$ 的获取方式遍历到 $s[j]$ 时初始化索引 $i j - 1$向左线性遍历搜索第一个满足 $s[i] s[j]$ 的字符即可。复杂度分析时间复杂度 $O(N^2)$其中 $N$ 为字符串长度动态规划需遍历计算 $dp$ 列表占用 $O(N)$每轮计算 $dp[j]$ 时搜索 $i$ 需要遍历 $j$ 个字符占用 $O(N)$。空间复杂度 $O(1)$几个变量使用常数大小的额外空间。代码Pythonclass Solution: def lengthOfLongestSubstring(self, s: str) - int: res tmp i 0 for j in range(len(s)): i j - 1 while i 0 and s[i] ! s[j]: i - 1 # 线性查找 i tmp tmp 1 if tmp j - i else j - i # dp[j - 1] - dp[j] res max(res, tmp) # max(dp[j - 1], dp[j]) return resJavaclass Solution { public int lengthOfLongestSubstring(String s) { int res 0, tmp 0, len s.length(); for(int j 0; j len; j) { int i j - 1; while(i 0 s.charAt(i) ! s.charAt(j)) i--; // 线性查找 i tmp tmp j - i ? tmp 1 : j - i; // dp[j - 1] - dp[j] res Math.max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } }Cclass Solution { public: int lengthOfLongestSubstring(string s) { int res 0, tmp 0, len s.size(); for(int j 0; j len; j) { int i j - 1; while(i 0 s[i] ! s[j]) i--; // 线性查找 i tmp tmp j - i ? tmp 1 : j - i; // dp[j - 1] - dp[j] res max(res, tmp); // max(dp[j - 1], dp[j]) } return res; } };仓库中的对应源文件Pythonsfo_48_the_longest_substring_without_repeated_characters_s2.pyJavasfo_48_the_longest_substring_without_repeated_characters_s2.javaCsfo_48_the_longest_substring_without_repeated_characters_s2.cpp五、方法三双指针 哈希表O(N) 时间与方法一本质等价不同点在于左边界 $i$ 的定义不同。哈希表 $dic$ 统计指针 $j$ 遍历字符 $s$哈希表统计字符 $s[j]$最后一次出现的索引。更新左指针 $i$根据上轮左指针 $i$ 和 $dic[s[j]]$每轮更新左边界 $i$保证区间 $[i 1, j]$ 内无重复字符且最大$$ i \max(dic[s[j]], i) $$更新结果 $res$取上轮 $res$ 和本轮双指针区间 $[i 1, j]$ 的宽度即 $j - i$中的最大值$$ res \max(res, j - i) $$与方法一的 DP 视角对照理解方法一维护的是“以 $j$ 结尾的最长长度tmp”方法三维护的是“合法窗口的左边界 $i$”两者每轮都在做同一件事——把窗口收缩到不含重复字符的最小合法范围再向外扩展。复杂度分析时间复杂度 $O(N)$双指针各遍历字符串一遍每轮哈希表操作为 $O(1)$。空间复杂度 $O(1)$字符的 ASCII 码范围为 $0 \sim 127$哈希表 $dic$ 最多使用 $O(128) O(1)$ 大小的额外空间。代码Pythonclass Solution: def lengthOfLongestSubstring(self, s: str) - int: dic, res, i {}, 0, -1 for j in range(len(s)): if s[j] in dic: i max(dic[s[j]], i) # 更新左指针 i dic[s[j]] j # 哈希表记录 res max(res, j - i) # 更新结果 return resJavaclass Solution { public int lengthOfLongestSubstring(String s) { MapCharacter, Integer dic new HashMap(); int i -1, res 0, len s.length(); for(int j 0; j len; j) { if(dic.containsKey(s.charAt(j))) i Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i dic.put(s.charAt(j), j); // 哈希表记录 res Math.max(res, j - i); // 更新结果 } return res; } }Cclass Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapchar, int dic; int i -1, res 0, len s.size(); for(int j 0; j len; j) { if(dic.find(s[j]) ! dic.end()) i max(i, dic.find(s[j])-second); // 更新左指针 dic[s[j]] j; // 哈希表记录 res max(res, j - i); // 更新结果 } return res; } };仓库中的对应源文件Pythonsfo_48_the_longest_substring_without_repeated_characters_s3.pyJavasfo_48_the_longest_substring_without_repeated_characters_s3.javaCsfo_48_the_longest_substring_without_repeated_characters_s3.cpp六、三种解法对比与仓库中如何运行验证复杂度总览解法时间复杂度空间复杂度核心机制暴力枚举$O(N^3)$$O(N)$判重枚举全部子串并逐一判重方法一DP 哈希表$O(N)$$O(1)$哈希表 O(1) 定位最近重复字符 $i$方法二DP 线性遍历$O(N^2)$$O(1)$每轮从 $j-1$ 向左线性搜索 $i$方法三双指针 哈希表$O(N)$$O(1)$维护无重复窗口 $[i1, j]$$i \max(dic[s[j]], i)$从源码结构看方法一与方法三的代码骨架几乎一致一个哈希表 一个整型滚动量 一次外层遍历只是滚动量的语义不同tmp是“以 $j$ 结尾的最长无重复子串长度”i是“当前合法窗口的左边界”。这也印证了原文档的结论两者本质等价方法三只是把 DP 状态“重新参数化”成了窗口左指针。仓库内的验证方式仓库对每个解法都提供了独立的、可单独运行的完整文件解法代码 测试用例 驱动代码三段落均以注释分隔测试用例统一为s abcabcbb该用例中不含重复字符的最长子串为abc三个解法均输出3。各语言目录下共 9 个文件3 种解法 × 3 种语言文件命名规则为sfo_48_the_longest_substring_without_repeated_characters_s{1,2,3}分别对应方法一、方法二、方法三。三种语言的运行环境约定从源码结构看Python每个.py文件顶部from include import *公共依赖链表、二叉树、打印工具位于 sword_for_offer/codes/python/include 目录直接python sfo_48_..._s1.py即可看到输出Java每个解法文件自带main方法并声明独立package公共类位于 sword_for_offer/codes/java/include 目录ListNode.java、TreeNode.java、PrintUtil.javaC每个解法文件自带main函数公共头文件为 include.hpp源文件通过#include ../include/include.hpp引用。小结本题是“以某位置结尾的最长子串”这一 DP 范式的典型题状态定义、三分支转移方程、取最大值得答案滚动变量tmp/res把空间从 $O(N)$ 降到 $O(1)$三种解法的差异只在于“如何找到 $s[j]$ 左边最近相同字符的索引 $i$”哈希表查询是 $O(1)$线性向左扫描是 $O(N)$双指针写法与 DP 写法本质等价面试中可根据表达习惯任选其一但需要能说明左边界更新的两个不变式区间内无重复、区间尽可能宽。同一题在 LeetCode 中对应“3. 无重复字符的最长子串”仓库在selected_coding_interview目录下也收录了它的多语言解法如 lc_3_longest_substring_without_repeating_characters_s1.py可与本文对照阅读。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考