0003. 无重复字符的最长子串 #
- 标签:字符串、哈希表、双指针、字符串、滑动窗口
- 难度:中等
题目大意 #
描述:给定一个字符串 s
。
要求:找出其中不含有重复字符的最长子串的长度。
说明:
- $0 \le s.length \le 5 * 10^4$。
s
由英文字母、数字、符号和空格组成。
示例:
|
|
解题思路 #
思路 1:滑动窗口(不定长度) #
用滑动窗口 window
来记录不重复的字符个数,window
为哈希表类型。
- 设定两个指针:
left
、right
,分别指向滑动窗口的左右边界,保证窗口中没有重复字符。 - 一开始,
left
、right
都指向0
。 - 向右移动
right
,将最右侧字符s[right]
加入当前窗口window
中,记录该字符个数。 - 如果该窗口中该字符的个数多于 1 个,即
window[s[right]] > 1
,则不断右移left
,缩小滑动窗口长度,并更新窗口中对应字符的个数,直到window[s[right]] <= 1
。 - 维护更新无重复字符的最长子串长度。然后继续右移
right
,直到right >= len(nums)
结束。 - 输出无重复字符的最长子串长度。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(| \sum |)$。其中 $\sum$ 表示字符集,$| \sum |$ 表示字符集的大小。