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