LEETCODE.3题解

题目

给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

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

示例 2:

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

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

提示:

  • 0 <= s.length <= 5 * 104

  • s 由英文字母、数字、符号和空格组成

题解

滑动窗口+哈希表解法

思路:维持一个滑动窗口,保持滑动窗口内不存在重复字符。

从第一个值开始遍历,计算每个字符之前有多长的无重复的字串(用left指针记录)

每个【字符:位置】写入哈希表中,当检测到哈希表重复的时候,说明已经有重复的值了,这时候需要检测滑动窗口的左边界大小,确定left的值。

然后在每轮中更新最大值即可。

该解法只需要一次遍历,时间复杂度O(n),存储空间复杂度线性增长,O(n):

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        length = len(s)
        if length < 2:
            return length
        # hashmap保存索引
        hashmap = {}
        maxLen = 0
        left = -1
        for i in range(length):
            if s[i] in hashmap:
                # 更新左指针
                left = max(left, hashmap[s[i]])
            # 更新索引
            hashmap[s[i]] = i
            maxLen = max(maxLen, i - left)
        return maxLen

dark
sans