leetcode-3-无重复字符的最长子串-题解:

使用双指针实现滑动窗口。

1、初始化滑动窗口ls_ch=set();

2、初始化变量left=0,代表滑动窗口最左边元素的索引;

3、初始化变量res=0,代表最大无重复字符的子串长度;

4、遍历字符串s;当s[right]出现在滑动窗口ls_ch中时,从滑动窗口的最左边依次删除元素直到s[right]并删除同时更新该窗口最左边元素的索引;将s[right]加入ls_ch。更新res的值为max(res,right-left+1)。

5、返回res。

核心:找到最近的与s[j]相等的元素的索引i且当前i必须大于上一轮的i,j-i为该子串的长度。返回这些子串的最大长度。

举例如下:

例1:abcabcbb

【a】bcabcbb:right=0,s[right]="a",滑动窗口为【a】,left=0,res=max(0,0-0+1)=1

【ab】cabcbb:right=1,s[right]="b",滑动窗口为【ab】,left=0,res=max(1,1-0+1)=2

【abc】abcbb:right=2,s[right]="c",滑动窗口为【abc】,left=0,res=max(2,2-0+1)=3

a【bca】bcbb:right=3,s[right]="a",滑动窗口为【bc】+a,left=1,res=max(3,3-1+1)=3

ab【cab】cbb:right=4,s[right]="b",滑动窗口为【ca】+b,left=2,res=max(3,4-2+1)=3

abc【abc】bb:right=5,s[right]="c",滑动窗口为【ab】+c,left=3,res=max(3,5-3+1)=3

abcab【cb】b:right=6,s[right]="b",滑动窗口为【c】+b,left=5,res=max(3,6-5+1)=3

abcabcb【b】:right=7,s[right]="b",滑动窗口为【】+b,left=7,res=max(3,7-7+1)=3

例2:abba

【a】bba:right=0,s[right]="a",滑动窗口为【a】,left=0,res=max(0,0-0+1)=1

【ab】ba:right=1,s[right]="b",滑动窗口为【ab】,left=0,res=max(1,2-0+1)=2

ab【b】a:right=2,s[right]="b",滑动窗口为【】+b,left=2,res=max(2,2-2+1)=2

ab【ba】:right=3,s[right]="a",滑动窗口为【b】+a,left=2,res=max(2,3-2+1)=2

上一篇:`掌握Python-PPTX,让PPt制作变得轻而易举!`


下一篇:postgresql14源码编译安装