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判断键是否存在。

代码

Python：

class 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 res

Java：

class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, 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; } }

C++：

class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, 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; } };

仓库中的对应源文件（含测试用例与驱动代码）：

Python：sfo_48_the_longest_substring_without_repeated_characters_s1.py
Java：sfo_48_the_longest_substring_without_repeated_characters_s1.java
C++：sfo_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)$：几个变量使用常数大小的额外空间。

代码

Python：

class 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 res

Java：

class 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; } }

C++：

class 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; } };

仓库中的对应源文件：

Python：sfo_48_the_longest_substring_without_repeated_characters_s2.py
Java：sfo_48_the_longest_substring_without_repeated_characters_s2.java
C++：sfo_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)$ 大小的额外空间。

代码

Python：

class 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 res

Java：

class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, 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; } }

C++：

class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, 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; } };

仓库中的对应源文件：

Python：sfo_48_the_longest_substring_without_repeated_characters_s3.py
Java：sfo_48_the_longest_substring_without_repeated_characters_s3.java
C++：sfo_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)$	维护无重复窗口 $[i+1, 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.java）；
C++：每个解法文件自带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），可与本文对照阅读。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考