0003. 无重复字符的最长子串 #

标签：字符串、哈希表、双指针、字符串、滑动窗口
难度：中等

题目大意 #

描述：给定一个字符串 s。

要求：找出其中不含有重复字符的最长子串的长度。

说明：

$0 \le s.length \le 5 * 10^4$。
s 由英文字母、数字、符号和空格组成。

示例：

1
2
3
4
5
6
7
8


输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。


输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

解题思路 #

思路 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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        window = dict()
        ans = 0

        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1

            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1

            ans = max(ans, right - left + 1)
            right += 1

        return ans

思路 1：复杂度分析 #

时间复杂度：$O(n)$。
空间复杂度：$O(| \sum |)$。其中 $\sum$ 表示字符集，$| \sum |$ 表示字符集的大小。