转码刷 LeetCode 笔记[1]：3.无重复字符的最长子串（python）
题目描述初次错解
看 B 站视频后，了解到“滑动窗口”思想，遂自己动手尝试
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
lenth = 0
max_lenth = 0
s = list(s)
str = []
for char in s:
right = 0
if char not in str:
str.append(char)
right += 1
lenth = len(str)
if lenth > max_lenth:
max_lenth = lenth
else:
str.remove(char)
left += 1
return max_lenth答案分析
输入"abcabcbb"，输出的是5，正确结果是3
输入"pwwkew"，输出4，正确结果是3
第二次的解法
下面是 AI 根据我的解法修正的答案：
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
lenth = 0
max_lenth = 0
seen = set()
for right in range(len(s)):
while s in seen:
seen.remove(s)
left += 1
seen.add(s)
lenth = right - left + 1
if lenth > max_lenth:
max_lenth = lenth
return max_lenth我错哪了呢？
没有真正维护滑动窗口的左边界，只是 left += 1，但 str 中并没有正确地移除所有在左边界左边的字符；
remove(char) 只会移除第一个匹配项，这会导致窗口状态不一致；
也没有用 left 来限制窗口范围，只是把它当成一个计数器。
观察我的答案和修正之后的答案，产生了几个问题：
[*]seen = set()为什么用set不用list，二者有什么区别？
[*]为什么seen.remove(s)能移除所有在左边界左边的字符，而str.remove(char)不能？
[*]while s in seen: 改成 for s in seen: 是不是没有区别？
[*]子串长度为什么用right - left + 1计算，而不用len(seen)计算？
[*]seen = set() 和 seen={} 有什么区别？
下面来逐一解答
1. seen = set()为什么用 set 不用 list，二者有什么区别？
特性setlist查找速度O(1)（哈希表实现）O(n)（线性扫描）是否允许重复❌ 不允许重复元素✅ 允许重复元素是否保持顺序❌ 不保持插入顺序（Python 3.7+ 中 set 会保留插入顺序，但不依赖它）✅ 保持插入顺序2. 为什么seen.remove(s)能移除所有在左边界左边的字符，而str.remove(char)不能？
str.remove(char)这行代码的意思是：从 list 中删除第一个等于 char 的元素；它不会删除所有在左边界左边的字符；它只是把第一次出现的那个字符删掉；所以窗口状态就乱了，并没有真正“滑动”窗口。
while s in seen:
seen.remove(s)
left += 1通过 while 循环，可以只要出现重复字符，就删掉一次该字符，并实现左边界右移，直到窗口中没有重复子串为止。
关于循环，进而又产生了新的问题
3. while s in seen: 改成 for s in seen: 是不是没有区别？
有区别！
语法层面的错误
for s in seen: 试图把 seen 中的每个元素赋值给 s，也就是试图修改原字符串 s 的内容 —— 这是不允许的（字符串是不可变的），会报错：
TypeError: 'str' object does not support item assignment
逻辑层面的错误
for 循环会遍历 set 中的每个元素，而不是只要重复就一直删。
4. 子串长度为什么用right - left + 1计算，而不用len(seen)计算？
right - left + 1 是窗口的实际长度，也就是从 left 到 right 之间的子串长度
len(seen) 是不重复的字符数量，当把题目改为“允许最多两个重复”时，len(seen)输出的结果就不是子串长度了
只是在这道题中，这两个值相等。
5. seen = set() 和 seen={} 有什么区别？
纯纯的基础不牢！刷题刷懵了！
seen = set()是创建一个空集合
seen={}是创建一个空字典
写法类型是否可哈希去重set()set✅ 是{}dict❌ 否
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]