一、前记(1/3)
今天还本来打算出一趟小远门,但是犹豫了一下。幸好犹豫了那么一下,今天我家这边大雨,所幸没有造成一年前的惨剧(嘿嘿!)今天窝在家里面看了一天的雨,我真的太爱看下雨了!!!
二、题目描述

这道题比我想的远远要有意思。我一开始没做是因为看难度这是一个中等题目。以为会比较难,但是如果使用Python的话,确实写起来不难。
三、解题思路
1、我的思路
其实我的思路比较简单,定义首(i)尾(l)两个计数点,再定义一个记录长度的length。通过反复的从头比较,可以比较出一个无重复字符的最长字串。
参考代码:
#enconding:utf-8
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
length=0
i=0
l=0
while l<len(s):
if s[l] not in s[i:l]:
l+=1
length=max(length,l-i)
else:
i+=1
return length
#as a checking
solution=Solution()
a="abcabcbb"
print(solution.lengthOfLongestSubstring(a))
2、别人的思路
(1)里面的师傅有人用了一个hash思想+双指针
参考代码:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans=0
left=0
right=0
hashset=set([])
n=len(s)
while left<n:
while right<n and s[right] not in hashset:
hashset.add(s[right])
ans=max(ans,right-left+1)
right+=1
hashset.remove(s[left])
left+=1
if n-left <ans:
break
return ans
(2)还有一个师傅做了一个很厉害的改版(参考链接)
参考代码:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start,res,newdic=-1,0,{}
for i,c in enumerate(s):#按循环顺序,把s中的元素挨个放到新的newdic里去
if c in newdic and newdic[c]>start:
start=newdic[c]#重新定位start指针
newdic[c]=i#给这个重复字母赋上顺序值
else:#newdic里还没有这个重复字母,且不需要重新定位指针(重复字母在start之前,说明已经算过了,略掉)
newdic[c]=i
res=max(res,i-start) #更新最大子串长度
return res
(3)还有一种思路让我感觉非常的好理解(参考链接)
def lengthOfLongestSubstring(self, s: str) -> int:
r = 0 # 右指针
rel = 0
s_len = len(s) # 字符串长度
if s_len == 0:
return 0
hash = {} # 哈希表 存元素
hash[s[0]] = 1
for l in range(s_len): # 左指针
# 右移右指针
while r + 1 < s_len and s[r+1] not in hash:
hash[s[r+1]] = 1
r += 1
# 到数组边界或者遇到重复的了
rel = max(rel, r-l+1)
del(hash[s[l]])
return rel
四、学到了什么?
(学会了怎么膜拜大佬)