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 由英文字母、数字、符号和空格组成

---

💡分析:

1、不含重复字符的子串

2、求最长子串的长度

🫤思路：

以“s = abcabcbb”为例，以下是手动处理过程：

a
ab
abc
abca  :字段重复，去除最左边的字符 a s[0]
bca
bcab  :字段重复，去除最左边的字符 b s[1]
cab 
cabc  :字段重复，去除最左边的字符 c s[2]
abc
abcb  :字段重复，去除最左边的字符 a s[3]
bcb   :字段重复，去除最左边的字符 b s[4]
cb
cbb   :字段重复，去除最左边的字符 c s[5]
bb    :字段重复，去除最左边的字符 b s[6]
b

综上所述：

1、需要一个循环遍历字段;

2、需要一个容器来存放子串字符，并通过该容器判断子串是否重复，考虑到子串可能很长，使用集合（set）比列表更适合，因为集合的查找性能更优；

3、需要一个变量，存放“子串最左边字符” 在“字段s”中的下标位置；

4、需要一个变量，用于存储最长子串的长度；

现在开始编写代码（python3）：

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 定义一个集合，存放子串的字符child_set = set()# 定义一个变量，存放子串最左边字符在字段中的下标,初始下标为0left = 0# 定义一个变量，存放子串最大长度,初始值为0max_len = 0# 循环遍历字段sfor sc in s:'''判断待添加字符加入集合是否会重复，如果重复，则删除子串最左侧字符'''# if sc in child_set:# child_set.remove(s[left])# left += 1'''因为删除的是最左侧的字符，而不是待添加字符，所以待添加字符在集合中可能还是会重复，所以这里需要一个while循环，而不是if'''while sc in child_set:child_set.remove(s[left])left += 1# 确保不重复后，将待添加字符，加入进集合child_set.add(sc)# 记录集合最大长度，即子串最大长度max_len = max(max_len,len(child_set))return max_len

然后，这就是 滑动窗口算法