3. 无重复字符的最长子串
type
status
date
slug
summary
tags
category
difficulty
icon
password
3. 无重复字符的最长子串
给定一个字符串
s ，请你找出其中不含有重复字符的 最长子串
的长度。
示例 1:
示例 2:
示例 3:
提示：
0 <= s.length <= 5 * 104
s由英文字母、数字、符号和空格组成
解题思路：使用滑动窗口法来解决这个问题
这道题使用滑动窗口的方法来解决，具体思路如下：
- 定义变量：
- 使用
res记录最长无重复子串的长度 - 使用哈希表
map记录每个字符出现的次数 - 使用两个指针
i和j分别表示窗口的右边界和左边界
- 滑动窗口处理：
- 右指针
i不断向右移动，将新字符加入窗口 - 每当加入新字符时，更新该字符在哈希表中的出现次数
- 如果某个字符出现次数大于1，说明出现了重复
- 通过移动左指针
j来缩小窗口，直到重复消失
- 更新结果：
- 在每次窗口调整后，计算当前窗口长度
i - j + 1 - 使用
max函数更新最大长度res
时间复杂度：O(n)，其中 n 是字符串的长度。左右指针最多各遍历一次字符串。
空间复杂度：O(k)，其中 k 是字符集的大小。哈希表需要存储不同字符的出现次数。
- 作者:Episkey
- 链接:https://episkey.top/article/longest-substring-without-repeating-characters
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
