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

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

题目大意 #

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

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

解题思路 #

用滑动窗口 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
 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