首页 » 运维 » 正文

leetCode 无重复字符的最长子串 python(Longest Substring Without Repeating Characters) python

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

 

这个题目是一个中等难度的题目:

核心的点就是如何去查找不重复的字符串(字符串不一定从头开始的最长)

下边用一张图来解释

long-1

如上图所示,我们要计算长度,肯定要知道这个非重复字符串的开始位置和结束位置,然后两者相减+1就能得到长度

我们肯定从第一种情况开始,从第一个字母开始查找非重复的字符串,我们的结束位置的指针一直在向前移动,每次移动都会判断如下的情况:

1:结束指针所指的位置上的元素是否与蓝色集合部分重复(蓝色数组为没有重复字符的一个集合),并根据实际情况进行判断,如果存在,更新开始位置指针

2:计算max的在值

3:结束指针操作

4:开始指针操作

如上图所示,开始指针位置一直没有变动,随着红色指针不断前移,数组不断变大(字符串长度不断变大),

直到遇到重复的字符A

当结束指针指向A的时候,这个时候判断是否存在我们的数组中的时候,这个时候已经存在,说明从A开始的最大字符串就是ABCDEF,最大长度也就是上次的循环中的Max的值,因为ABCDEFA这个字符串开始不符合规则,存在重复字符A,那么我接下来应该开始从第二个位置开始重新判断

long-1-2

然后,我们两个指针都指向B,然后开始保持开始指针不动,逐个移动结束指针,如上图所示,我们找到的最大字符串也开始B->BC->BCD->BCDE->BCDEF->BCEDFA

这个时候我们就发现了一个问题,感觉哪里好像做了无用功,第一次查找中我们已经确定了ABCDEF中没有重复元素,那么它的子集BCDEF肯定没有重复的,所以我们从B开始比较的时候,可以直接从第二个A的位置开始,不用结束位置重置

 

但是,我们该从什么位置开始第二次比较呢?第二个么?山边的例子是个特例,我们看下边的情况

long-2

 

这次我们发现,如果按照开始指针前移1位的情况,这个就不适用了,因为如果你前移1位,我们知道ABCDEF没有重复,也知道BCDEF也没有重复,但是BCDEFB就有重复了,也就是说

ABCDEFB有重复 –>BCDEFB有重复还少了1位,也就是说,从B开始比较完全没有意思,因为他最大的非重复字符型BCDEF肯定比它的上一次ABCDEF少,所以我们开始的位置不是后移一位,而是,后移到第一个B的后边,也就是从C的位置开始重新排查,结束的位置也不需要重置

再加一个情况大家看一下:

 

 

long-3

 

 

代码部分:

 

发表评论