一、前记(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

四、学到了什么?

(学会了怎么膜拜大佬)