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

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

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

题目大意 #

描述:给定一个字符串 s

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

解题思路 #

用滑动窗口 window 来记录不重复的字符个数,window 为哈希表类型。

设定两个指针:leftright,分别指向滑动窗口的左右边界,保证窗口中没有重复字符。

  • 一开始,leftright 都指向 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
本站总访问量  次  |  您是本站第  位访问者