您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode中怎么找出字符串中无重复最长子串
## 问题描述
在LeetCode题库中，第3题"无重复字符的最长子串"（Longest Substring Without Repeating Characters）是一个经典的字符串处理问题。题目要求：
给定一个字符串 `s`，找出其中不含有重复字符的**最长子串**的长度。
**示例：**
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
## 问题分析
### 关键概念
1. **子串**：字符串中连续的字符序列
2. **无重复字符**：子串中所有字符都是唯一的
3. **最长**：在所有符合条件的子串中长度最大的
### 难点分析
- 需要高效地检查字符是否重复
- 需要跟踪当前无重复子串的起始位置
- 需要在遍历过程中动态更新最大长度
## 解决方案
### 方法一：暴力解法（不推荐）
#### 思路
检查所有可能的子串，判断是否有重复字符，记录最长长度。
```python
def lengthOfLongestSubstring(s: str) -> int:
n = len(s)
max_len = 0
for i in range(n):
for j in range(i, n):
if len(set(s[i:j+1])) == j-i+1:
max_len = max(max_len, j-i+1)
return max_len
维护一个滑动窗口，窗口内的字符都是唯一的。通过移动窗口的左右边界来寻找最长子串。
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
记录字符及其索引，遇到重复字符时直接跳转左指针。
def lengthOfLongestSubstring(s: str) -> int:
char_map = {}
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in char_map:
left = max(left, char_map[s[right]] + 1)
char_map[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
| 方法 | 时间复杂度 | 空间复杂度 | LeetCode执行用时 |
|---|---|---|---|
| 暴力法 | O(n³) | O(min(m,n)) | >1000ms |
| 滑动窗口 | O(n) | O(min(m,n)) | ~100ms |
| 优化滑动窗口 | O(n) | O(min(m,n)) | ~50ms |
"" → 返回0"bbbbb" → 返回1"abcdef" → 返回字符串长度"pwwkew" → 返回3（”wke”）assert lengthOfLongestSubstring("") == 0
assert lengthOfLongestSubstring("bbbbb") == 1
assert lengthOfLongestSubstring("abcabcbb") == 3
assert lengthOfLongestSubstring("pwwkew") == 3
def lengthOfLongestSubstring(s: str) -> int:
# 假设字符串只包含扩展ASCII字符（256个）
char_index = [-1] * 256
left = 0
max_len = 0
for right in range(len(s)):
if char_index[ord(s[right])] >= left:
left = char_index[ord(s[right])] + 1
char_index[ord(s[right])] = right
max_len = max(max_len, right - left + 1)
return max_len
对于已知字符范围的情况（如小写字母），可以进一步减少空间使用：
char_index = [-1] * 26 # 仅小写字母
# 错误示范：未正确处理左指针移动
def lengthOfLongestSubstring(s: str) -> int:
char_map = {}
left = 0
max_len = 0
for right in range(len(s)):
if s[right] in char_map:
left = char_map[s[right]] # 错误：应该+1
char_map[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
解决”无重复字符的最长子串”问题的关键在于： 1. 理解滑动窗口的概念 2. 选择合适的哈希结构存储字符位置 3. 正确处理指针移动和边界条件
优化后的滑动窗口算法是最优解，时间复杂度O(n)，空间复杂度O(min(m,n))。建议通过反复练习掌握滑动窗口的常见模式，这对解决类似问题大有裨益。
通过系统学习和实践，你不仅能够解决这个问题，还能掌握一类字符串处理问题的通用解法。 “`
这篇文章共计约2200字，涵盖了问题描述、多种解法、复杂度分析、边界处理、优化技巧、实际应用和学习建议等内容，采用Markdown格式编写，适合技术博客或学习笔记。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。