题目
给定一个字符串 s，找出其中不含重复字符的最长子串的长度。子串必须是原字符串中连续的一段。
示例 1：
❯Text
输入：s = "abcabcbb"
输出：3
解释：最长无重复子串可以是 "abc"、"bca" 或 "cab"。示例 2：
❯Text
输入：s = "bbbbb"
输出：1示例 3：
❯Text
输入：s = "pwwkew"
输出：3
解释：答案是 "wke"；"pwke" 不是连续子串。提示：
0 <= s.length <= 10^5s由英文字母、数字、符号和空格组成
考察内容
- 滑动窗口的扩张与收缩
- 使用哈希集合维护窗口内字符
- 使用哈希表记录字符最近出现的位置
- 连续子串与子序列的区别
- 窗口不变量与边界更新
解题思路
滑动窗口 + 哈希集合
使用闭区间 [left, right] 表示当前窗口，并用哈希集合保存窗口内出现的字符。始终维护不变量：窗口内没有重复字符。
当右指针准备加入 s[right] 时：
- 如果字符不在集合中，直接加入并更新最大窗口长度；
- 如果字符已经存在，就不断删除左端字符并右移
left； - 直到重复字符被移出窗口，再加入
s[right]。
必须使用 while 收缩，因为重复字符不一定恰好位于窗口左端。例如窗口为 "abca" 时，需要连续移除 a 之前的所有字符以及旧的 a。
以 s = "abcabcbb" 为例：
right | 加入字符 | 收缩后的窗口 | 当前最大长度 |
|---|---|---|---|
| 0 | a | a | 1 |
| 1 | b | ab | 2 |
| 2 | c | abc | 3 |
| 3 | a | bca | 3 |
| 4 | b | cab | 3 |
| 5 | c | abc | 3 |
| 6 | b | cb | 3 |
| 7 | b | b | 3 |
每个字符最多进入和离开集合一次，因此：
- 时间复杂度：
- 空间复杂度：，
k为字符集大小，最坏为
最近位置跳转
进一步使用哈希表记录每个字符最近出现的下标。若 s[right] 曾经出现在当前窗口内，可以令：
这样左边界可以一次跳过旧的重复字符，不必逐个删除。这里必须取 max，否则字符上一次出现的位置若已经在窗口左侧，会让 left 错误地向后退。
代码演示
❯C++
// 写法一：哈希集合维护窗口中的字符
int lengthOfLongestSubstring(const std::string& s) {
std::unordered_set<char> window;
int left = 0;
int result = 0;
for (int right = 0; right < static_cast<int>(s.size()); ++right) {
while (window.count(s[right])) {
window.erase(s[left]);
++left;
}
window.insert(s[right]);
result = std::max(result, right - left + 1);
}
return result;
}
// 写法二：记录最近下标，让 left 直接跳转
int lengthOfLongestSubstringJump(const std::string& s) {
std::unordered_map<char, int> last;
int left = 0;
int result = 0;
for (int right = 0; right < static_cast<int>(s.size()); ++right) {
auto it = last.find(s[right]);
if (it != last.end()) {
left = std::max(left, it->second + 1);
}
last[s[right]] = right;
result = std::max(result, right - left + 1);
}
return result;
}易错点
- 把子串理解成子序列：子串必须连续，不能跳过中间字符。
- 用
if代替while收缩窗口：移除一个左端字符后，重复字符可能仍在窗口内。 - 加入重复字符后才收缩：集合写法应先排除旧字符，再插入当前字符，才能维护窗口无重复的不变量。
- 窗口长度少算一位：闭区间
[left, right]的长度是right - left + 1。 - 跳转写法让
left后退：必须使用max(left, last[c] + 1)。 - 空字符串处理错误：循环不会执行，初始答案
0正好符合要求。
总结
本题是滑动窗口的经典模型：右指针负责扩张，发现重复字符时左指针负责收缩，窗口始终保持无重复。集合写法更直观；最近位置写法可以让左边界一步跳转。
相关题目
-
- 最小覆盖子串
-
- 至多包含两个不同字符的最长子串
-
- 长度最小的子数组
-
- 替换后的最长重复字符
-
- 水果成篮