leetcode with python:3. Longest Substring Without Repeating

题目:

Given a string s, find the length of the longest substring without repeating characters.

给定一个字串,回传其中最大的无重複字元字串长度

我们的第二题medium,题目简单暴力,我一开始没什么头绪,脑中满满的超时暴力解,直到在related topics中看到sliding window这个陌生的字眼
上网搜寻了一下,发现原来是所谓的「滑动窗口演算法」,深入了解后,对这题也开始有了头绪

那我们简单讲一下滑动窗口演算法(sliding window)是什么:
这个演算法主要用在list资料的处理上,要实作我们需要两个指标储存index分别代表窗口的两侧,而两个指标中间便是我们要操作的窗口
透过指标的移动,我们就能变更窗口的大小及涵盖内容,至于它会怎样提高我们程式效率,我这边举个例来说明:

给一个list[1,2,3,4,5]然后我们要找出所有连续三数的合,最直接的解法就是取 index 0,1,2相加,1,2,3相加......而使用sliding window的话,我们先宣两个指标(start->s表示,end->e表示),让它们都在index 0开始[1(s)(e),2,3,4,5],接着让e开始往后移,一边把e位置的值加到sum,我们可以透过s,e的距离来推算当前窗口的大小当窗口大小达到3[1(s),2,3(e),4,5],我们便可以记录当前的sum,接着继续移动e,会导致窗口>3,于是我们将s值往前移,将窗口大小重新降为3,同时sum减掉s离开位置的值[1,2(s),3,4(e),5],此时sum又是另一个连续三数合我们持续如此记录值到e到达阵列最尾端,我们便取得所有连续三数合

法一跟法二差在前者重複取值计算,而后者透过前端尾端的加减重複利用了中间的值,一旦资料变得巨大,两者的效率差就会更为明显

有了这种思考模式,我成功构筑出我的程式

class Solution:    def lengthOfLongestSubstring(self, s: str) -> int:        s1=set()        ans=0        start=0        end=0                while True:            if end>len(s)-1:                return ans                            if s[end] in s1:                if len(s1)>ans:                    ans=len(s1)                s1.remove(s[start])                start=start+1                            if s[end] not in s1:                s1.add(s[end])                if end==(len(s)-1):                    if len(s1)>ans:                        ans=len(s1)                   end=end+1

我这边用了类似1.法二的模式结合sliding window
一边移动窗口一边将路过的字元纪录到set内
end所在位置的值如果不在set内就纪录后end继续往前
在set内end就停止而start要往前移动且在set中remove离开位置的值,在此之前纪录当下len(set)的值
因为end碰触到set里有的值的那刻,len(set)便是最大无重複字元字串长度的其中一种可能(因为到目前为止字元无重複),我们将其记录
接着start会持续往前持续remove,直到end接触的值不在set内,end再继续前进纪录,重複模式,直到尾端
过程中纪录到最大的len(set)就是最大无重複字元字串长度,也是我们要回传的值
最后执行时间67ms(faster than 87.71%)

本题学习到的重点:sliding window
那我们下题见