力扣-3. 无重复字符的最长子串

题目描述

思路及实现

找一个不含有重复字符的最长字串，由不重复字符我们可以想到哈希表，在遍历字符串的时候，遇到一个字符就判断这个字符在不在哈希表里边，如果在就说明出现重复字符，此时可以计算子串的长度（两个重复字符的索引相减）。
然后为了节省时间复杂度，我们可以使用滑动窗口来防止重复遍历。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        left = right = 0
        a_dict = {}
        n = len(s)
        while right < n:
            if s[right] not in a_dict:  # 字典中未查到该字符出现过
                a_dict[s[right]] = right  # 记录索引位置
                right += 1
            else:
                if (right - left) > result:  # 更新最大值
                    result = right - left
                if left < a_dict[s[right]] + 1:
                    left = a_dict[s[right]] + 1
                a_dict.pop(s[right])
        if right - left > result:  # 更新最大值
            result = right - left
        return result

但是我们可以发现，在检查到重复字符出现后，其实并不需要弹出相应键值对，我们可以直接在检查每个字符的时候更新左指针索引，左指针是不需要回头看的，只会往右走。
然后更新结果，最后更新字典中当前字符的索引即可。
优化后的另一种写法：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        left = right = 0
        a_dict = {}
        n = len(s)
        for right in range(n):
            if s[right] in a_dict:  # 字典中查到该字符出现过
                left = max(left, a_dict[s[right]])
            result = max(result, right - left + 1)
            a_dict[s[right]] = right + 1  # 记录索引位置
        return result

---

希望本文章能够帮到您~