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

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

---

示例

示例 1:

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

示例 2:

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

示例 3:

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

---

解法

这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要找到那个相同元素的位置，把队列中它左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0 # 如果字符串s为空，返回0
        lookup = [] # 初始化窗口
        max_len = 0 # 窗口长度
        cur_len = 0 # 当前子串长度
       
        for i in range(len(s)): # 遍历字符串s
            val = s[i]
            if not val in lookup: # 如果该值不在窗口中
                lookup.append(val) # 添加到窗口内
                cur_len += 1  # 当前长度+1
            else:# 如果该值在窗口中已存在
                index = lookup.index(val) # 获取其在窗口中的位置
                lookup = lookup[index+1:] # 移除该位置及之前的字符
                lookup.append(val) 
                cur_len = len(lookup) # 当前长度更新为窗口长度
            
            if cur_len > max_len: # 看是否需要更新最大长度值
                max_len = cur_len
        
        return max_len # 返回最大子串长度

---

来源

LeetCode中该题地址，Click here!