跳至主要內容

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

ITCharge大约 2 分钟

0003. 无重复字符的最长子串open in new window

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

题目链接

题目大意

描述:给定一个字符串 ss

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

说明

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

示例

  • 示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3
  • 示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1

解题思路

思路 1:滑动窗口(不定长度)

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

  1. 设定两个指针:leftleftrightright,分别指向滑动窗口的左右边界,保证窗口中没有重复字符。
  2. 一开始,leftleftrightright 都指向 00
  3. 向右移动 rightright,将最右侧字符 s[right]s[right] 加入当前窗口 windowwindow 中,记录该字符个数。
  4. 如果该窗口中该字符的个数多于 11 个,即 window[s[right]]>1window[s[right]] > 1,则不断右移 leftleft,缩小滑动窗口长度,并更新窗口中对应字符的个数,直到 window[s[right]]1window[s[right]] \le 1
  5. 维护更新无重复字符的最长子串长度。然后继续右移 rightright,直到 rightlen(nums)right \ge len(nums) 结束。
  6. 输出无重复字符的最长子串长度。

思路 1:代码

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(n)
  • 空间复杂度O()O(| \sum |)。其中 \sum 表示字符集,| \sum | 表示字符集的大小。