惠州市网站建设_网站建设公司_需求分析_seo优化

LeetCode 3. 无重复字符的最长子串

---

一、题目描述

原题

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

示例

示例	输入	输出	解释
1	s = "abcabcbb"	3	最长子串是 "abc"，长度为 3
2	s = "bbbbb"	1	最长子串是 "b"，长度为 1
3	s = "pwwkew"	3	最长子串是 "wke"，长度为 3

约束条件

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

---

二、题目解析

核心问题拆解

维度	分析内容
输入	字符串 s，可能为空，包含 ASCII 字符
输出	整数，表示最长无重复子串的长度
子串 vs 子序列	子串必须是连续的，子序列可以不连续
无重复	窗口内每个字符只能出现一次
边界条件	空字符串返回0，单字符返回1

思考方向流程图

flowchart TDA[原问题: 最长无重复子串] --> B{如何遍历所有子串?}B --> C[方法1: 暴力枚举]B --> D[方法2: 滑动窗口]C --> C1[枚举所有起点i]C1 --> C2[枚举所有终点j]C2 --> C3[检查i,j间是否有重复]C3 --> C4[时间复杂度 O(n³)]D --> D1[维护一个窗口]D1 --> D2{窗口内有重复?}D2 -->|是| D3[收缩左边界]D2 -->|否| D4[扩展右边界]D3 --> D5[更新最大长度]D4 --> D5D5 --> D6[时间复杂度 O(n)]style A fill:#e1f5festyle D6 fill:#c8e6c9style C4 fill:#ffcdd2

---

三、算法解答

---

解法一：暴力枚举法

1. 算法原理描述

核心思想：枚举所有可能的子串，检查每个子串是否包含重复字符，记录最长的无重复子串长度。

实现方式：

• 外层循环枚举子串起点 i
• 内层循环枚举子串终点 j
• 使用集合检查子串 [i, j] 是否有重复字符

2. 算法解答过程

以 s = "abcab" 为例：

起点i	终点j	子串	是否有重复	当前最大长度
0	0	"a"	否	1
0	1	"ab"	否	2
0	2	"abc"	否	3
0	3	"abca"	是(a重复)	3
1	1	"b"	否	3
1	2	"bc"	否	3
1	3	"bca"	否	3
1	4	"bcab"	是(b重复)	3
...	...	...	...	...

3. 算法原理图像解析

flowchart LRsubgraph 暴力枚举过程A["字符串: a b c a b"] --> B[枚举起点 i=0]B --> C[枚举终点 j=0,1,2...]C --> D{检查重复}D -->|无重复| E[更新最大值]D -->|有重复| F[跳出内循环]E --> G[j++继续]F --> H[i++下一起点]end

4. 算法代码

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();int maxLen = 0;// 枚举所有子串的起点for (int i = 0; i < n; i++) {// 枚举所有子串的终点for (int j = i; j < n; j++) {// 检查子串 s[i..j] 是否有重复字符if (allUnique(s, i, j)) {maxLen = max(maxLen, j - i + 1);}}}return maxLen;}private:// 检查子串 s[start..end] 是否所有字符都唯一bool allUnique(const string& s, int start, int end) {unordered_set<char> charSet;for (int i = start; i <= end; i++) {if (charSet.count(s[i])) {return false;  // 发现重复}charSet.insert(s[i]);}return true;}
};

5. 代码详解

关键点	说明
unordered_set	用于O(1)时间检查字符是否存在
双重循环	外层枚举起点，内层枚举终点
allUnique	辅助函数检查子串是否无重复

常见问题：

• 时间复杂度过高，大数据会超时
• 重复检查了很多子串

6. 复杂度分析

复杂度类型	值	说明
时间复杂度	O(n³)	两层循环 O(n²) × 检查重复 O(n)
空间复杂度	O(min(n, m))	m 为字符集大小

7. 使用范围

• 仅适用于理解题目
• 数据量小（n < 100）时可用
• 不推荐在面试中使用

---

解法二：滑动窗口 + HashSet

1. 算法原理描述

核心思想：使用两个指针维护一个滑动窗口，窗口内的字符始终保持无重复。

实现方式：

• left 指针：窗口左边界
• right 指针：窗口右边界
• 当遇到重复字符时，移动 left 直到消除重复
• 使用 HashSet 记录窗口内的字符

2. 算法解答过程

以 s = "abcabcbb" 为例：

步骤	left	right	当前字符	窗口内容	Set内容	操作	最大长度
1	0	0	'a'	"a"		加入a	1
2	0	1	'b'	"ab"		加入b	2
3	0	2	'c'	"abc"		加入c	3
4	0	3	'a'	-		a重复,删a,left++	3
5	1	3	'a'	"bca"		加入a	3
6	1	4	'b'	-		b重复,删b,left++	3
7	2	4	'b'	"cab"		加入b	3
8	2	5	'c'	-		c重复,删c,left++	3
...	...	...	...	...	...	...	...

3. 算法原理图像解析

flowchart TDsubgraph 滑动窗口过程A[初始化 left=0, right=0] --> B{right < n ?}B -->|是| C{s[right] 在窗口中?}C -->|否| D[将 s[right] 加入Set]D --> E[更新 maxLen]E --> F[right++]F --> BC -->|是| G[从Set删除 s[left]]G --> H[left++]H --> CB -->|否| I[返回 maxLen]endstyle A fill:#e3f2fdstyle I fill:#c8e6c9

4. 算法代码

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();unordered_set<char> window;  // 存储窗口内的字符int left = 0, right = 0;     // 双指针int maxLen = 0;while (right < n) {// 如果当前字符在窗口中存在，收缩左边界while (window.count(s[right])) {window.erase(s[left]);left++;}// 将当前字符加入窗口window.insert(s[right]);// 更新最大长度maxLen = max(maxLen, right - left + 1);// 扩展右边界right++;}return maxLen;}
};

5. 代码详解

关键点	说明
window	HashSet存储当前窗口内的字符
内层while	当有重复时，不断收缩左边界
right - left + 1	当前窗口大小

为什么正确：

• 每次 right 移动前，保证窗口内无重复
• 通过收缩 left 来消除重复字符

6. 复杂度分析

复杂度类型	值	说明
时间复杂度	O(n)	left和right各遍历一次，最多2n次操作
空间复杂度	O(min(n, m))	m为字符集大小(ASCII为128)

7. 使用范围

• 通用解法，适用于大多数情况
• 面试首选方案
• 易于理解和实现

---

解法三：滑动窗口 + HashMap（最优化）

1. 算法原理描述

核心思想：使用 HashMap 记录每个字符最后出现的位置，当遇到重复字符时，可以直接跳转 left 指针，而不是逐步移动。

实现方式：

• map[char] 存储字符 char 最后出现的下标
• 遇到重复时：left = max(left, map[s[right]] + 1)
• 直接跳过所有需要删除的字符

2. 算法解答过程

以 s = "abcabcbb" 为例：

步骤	left	right	字符	map状态	操作	最大长度
1	0	0	'a'		加入	1
2	0	1	'b'		加入	2
3	0	2	'c'		加入	3
4	1	3	'a'		a在0,left跳到1	3
5	2	4	'b'		b在1,left跳到2	3
6	3	5	'c'		c在2,left跳到3	3
7	5	6	'b'		b在4,left跳到5	3
8	7	7	'b'		b在6,left跳到7	3

3. 算法原理图像解析

flowchart TDA[初始化 left=0, maxLen=0] --> B[遍历 right: 0 到 n-1]B --> C{s[right] 在map中<br>且位置 >= left?}C -->|是| D["left = map[s[right]] + 1<br>(直接跳转!)"]C -->|否| E[保持left不变]D --> F["更新 map[s[right]] = right"]E --> FF --> G["maxLen = max(maxLen, right-left+1)"]G --> H{right < n-1?}H -->|是| BH -->|否| I[返回 maxLen]style D fill:#fff9c4style I fill:#c8e6c9

4. 算法代码

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();unordered_map<char, int> lastIndex;  // 字符 -> 最后出现的位置int left = 0;int maxLen = 0;for (int right = 0; right < n; right++) {char c = s[right];// 如果字符存在且在当前窗口内，跳转leftif (lastIndex.count(c) && lastIndex[c] >= left) {left = lastIndex[c] + 1;}// 更新字符的最新位置lastIndex[c] = right;// 更新最大长度maxLen = max(maxLen, right - left + 1);}return maxLen;}
};

5. 代码详解

关键点	说明
lastIndex[c] >= left	必须检查位置是否在当前窗口内
left = lastIndex[c] + 1	直接跳转，跳过重复字符
单层循环	只有right指针在移动

易错点：

// ❌ 错误：没有检查是否在窗口内
if (lastIndex.count(c)) {left = lastIndex[c] + 1;
}// ✅ 正确：必须检查 lastIndex[c] >= left
if (lastIndex.count(c) && lastIndex[c] >= left) {left = lastIndex[c] + 1;
}

6. 复杂度分析

复杂度类型	值	说明
时间复杂度	O(n)	只遍历一次字符串
空间复杂度	O(min(n, m))	m为字符集大小

7. 使用范围

• 最优解法
• 适用于需要极致性能的场景
• 面试中的加分项

---

解法四：数组优化（ASCII字符集）

1. 算法原理描述

核心思想：当字符集有限（如ASCII 128个字符）时，用数组替代HashMap，获得更好的常数性能。

2. 算法代码

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.length();// 用数组存储字符最后出现的位置+1// index[c] = 0 表示字符c未出现过// index[c] = i 表示left至少应该从i开始vector<int> index(128, 0);int left = 0;int maxLen = 0;for (int right = 0; right < n; right++) {char c = s[right];// 更新left，取较大值保证单调性left = max(left, index[c]);// 更新最大长度maxLen = max(maxLen, right - left + 1);// 记录当前字符的下一个位置index[c] = right + 1;}return maxLen;}
};

3. 代码详解

关键点	说明
vector<int> index(128, 0)	128个ASCII字符，初始化为0
index[c] = right + 1	存储的是"下一个有效起点"
left = max(left, index[c])	保证left单调不减

技巧：存储 right + 1 而不是 right，省去了检查字符是否存在的步骤。

4. 复杂度分析

复杂度类型	值	说明
时间复杂度	O(n)	单次遍历
空间复杂度	O(1)	固定128大小的数组

---

四、算法对比

解法	时间复杂度	空间复杂度	优点	缺点	推荐指数
暴力枚举	O(n³)	O(n)	直观易懂	效率极低，会超时	⭐
滑动窗口+Set	O(n)	O(n)	思路清晰，易实现	收缩时逐个删除	⭐⭐⭐⭐
滑动窗口+Map	O(n)	O(n)	直接跳转，更高效	实现稍复杂	⭐⭐⭐⭐⭐
数组优化	O(n)	O(1)	常数最优	仅适用于有限字符集	⭐⭐⭐⭐⭐

推荐选择

flowchart LRA[选择解法] --> B{面试场景?}B -->|是| C{时间紧张?}B -->|否| D[数组优化版]C -->|是| E[滑动窗口+Set]C -->|否| F[滑动窗口+Map]style E fill:#c8e6c9style F fill:#c8e6c9style D fill:#fff9c4

---

五、知识点总结

涉及的数据结构

数据结构	用途	时间复杂度
HashSet	存储窗口内字符，判断重复	查找/插入/删除 O(1)
HashMap	存储字符最后位置	查找/更新 O(1)
数组	替代HashMap（有限字符集）	O(1)

涉及的算法思想

mindmaproot((滑动窗口))定义双指针维护区间窗口内满足某条件适用场景连续子数组/子串问题最长/最短满足条件的区间关键操作扩展右边界收缩左边界更新答案变体固定大小窗口可变大小窗口多条件窗口相关技巧哈希表记录频次双端队列维护极值前缀和优化

相关语言知识点

C++ 知识点	说明
unordered_set	哈希集合，O(1)查找
unordered_map	哈希表，O(1)存取
vector<int>(128, 0)	初始化固定大小数组
max()	取最大值函数
.count()	检查元素是否存在
.erase()	删除元素
.insert()	插入元素

---

六、做题模板

滑动窗口通用模板

// 滑动窗口模板 - 求最长满足条件的子串
int slidingWindowMaxLength(string s) {int n = s.length();unordered_map<char, int> window;  // 窗口内字符统计int left = 0, right = 0;int maxLen = 0;while (right < n) {char c = s[right];  // 即将进入窗口的字符right++;            // 扩大窗口// ... 更新窗口内数据 ...window[c]++;// 判断是否需要收缩窗口while (/* 窗口需要收缩的条件 */) {char d = s[left];  // 即将离开窗口的字符left++;            // 缩小窗口// ... 更新窗口内数据 ...window[d]--;}// 更新答案maxLen = max(maxLen, right - left);}return maxLen;
}

滑动窗口流程图

flowchart TDA[初始化 left=0, right=0] --> B{right < n?}B -->|是| C[获取 s[right], right++]C --> D[更新窗口数据]D --> E{需要收缩?}E -->|是| F[获取 s[left], left++]F --> G[更新窗口数据]G --> EE -->|否| H[更新答案]H --> BB -->|否| I[返回答案]style A fill:#e3f2fdstyle I fill:#c8e6c9

---

七、相关题目推荐

题号	题目名称	难度	关联知识点
76	最小覆盖子串	困难	滑动窗口 + HashMap
159	至多包含两个不同字符的最长子串	中等	滑动窗口 + 字符计数
340	至多包含K个不同字符的最长子串	中等	滑动窗口 + HashMap
395	至少有K个重复字符的最长子串	中等	分治 / 滑动窗口
424	替换后的最长重复字符	中等	滑动窗口 + 计数
438	找到字符串中所有字母异位词	中等	固定窗口 + HashMap
567	字符串的排列	中等	固定窗口 + HashMap
904	水果成篮	中等	滑动窗口（同159）
1004	最大连续1的个数 III	中等	滑动窗口 + 翻转计数
1695	删除子数组的最大得分	中等	滑动窗口（本题变体）

---

八、面试高频问答

Q1: 为什么用滑动窗口而不用动态规划？

答：

• 本题要求的是连续子串，滑动窗口天然维护连续区间
• DP适合有最优子结构的问题，本题没有明显的状态转移方程
• 滑动窗口时间复杂度O(n)，空间复杂度可做到O(1)，更优

Q2: left = max(left, index[c] + 1) 为什么要取max？

答：因为HashMap中存储的是历史信息，可能记录的位置在当前窗口左边界的左侧。

示例: s = "abba"
当right=3(字符'a')时:
- left=2
- index['a']=0 (之前记录的)
- 如果不取max: left = 0+1 = 1 ❌ (left反而变小了)
- 取max: left = max(2, 1) = 2 ✅

Q3: 如何处理Unicode字符？

答：

• 不能用固定大小数组，改用HashMap
• C++中可用 unordered_map<char32_t, int> 或 unordered_map<wchar_t, int>
• 空间复杂度变为O(min(n, m))，m为字符集大小

Q4: 这道题有哪些变体？

答：

变体	修改点
最多K个重复字符	收缩条件改为 count[c] > K
最多K种不同字符	收缩条件改为 window.size() > K
返回子串本身	记录 start 和 maxLen，最后截取

Q5: 能否用双指针从两端向中间？

答：不能。因为：

• 本题是"最长无重复子串"，需要遍历所有可能的窗口
• 双端指针通常用于有序数组的两数和问题
• 滑动窗口（同向双指针）才是正确的模式

Q6: 时间复杂度真的是O(n)吗？

答：是的。虽然有内层while循环，但：

• left 指针只会向右移动，最多移动n次
• right 指针也只向右移动，最多移动n次
• 总操作次数最多2n，仍是O(n)

---

九、一图总结

flowchart TBsubgraph 核心要点A[无重复最长子串] --> B[滑动窗口]B --> C[双指针: left, right]C --> D[HashSet/HashMap记录窗口]endsubgraph 关键操作E[扩展] --> E1[right++, 加入字符]F[收缩] --> F1[left++, 移除字符]G[更新] --> G1[maxLen = max...]endsubgraph 记忆口诀H["🔑 口诀"]H --> H1["右扩左缩滑窗移"]H --> H2["遇重则缩保唯一"]H --> H3["Map记位跳得快"]H --> H4["数组优化最极致"]endsubgraph 复杂度I[时间 O-n-] --- J[空间 O-1-/O-n-]endstyle A fill:#e1f5festyle H fill:#fff9c4style I fill:#c8e6c9style J fill:#c8e6c9

速记卡片

┌─────────────────────────────────────────┐
│ LeetCode 3 - 无重复最长子串 │
├─────────────────────────────────────────┤
│ 模式: 滑动窗口（可变大小） │
│ 数据结构: HashSet / HashMap / 数组 │
│ 时间: O(n) 空间: O(1) ~ O(n) │
├─────────────────────────────────────────┤
│ 核心代码: │
│ while (window.count(s[right])) │
│ window.erase(s[left++]); │
│ window.insert(s[right]); │
│ maxLen = max(maxLen, right-left+1); │
├─────────────────────────────────────────┤
│ 易错点: │
│ ✗ 忘记检查字符是否在当前窗口内 │
│ ✓ left = max(left, map[c]+1) │
└─────────────────────────────────────────┘

---

💡 面试建议：先写出滑动窗口+HashSet的解法，再优化到HashMap直接跳转，最后提及数组优化。展示渐进优化的思维过程。