leetcode上看到的题,就是给定一个字符串,找出不含重复字符的最长串的长度,例如abcabcc中的就是abc,bbbb中的就是b。

思路分析

这个如果用常规暴力计算当然比较麻烦,看别人的思路很厉害,用的是滑动窗口的思路去解决的。

滑动窗口就是用两个变量标识位置,分别为i和j,其中j只负责进,i负责出,如果发现一个元素是新的,那么j++,进一个,如果不是新的i++,出一个,具体演示过程如下:

background Layer 1 abbac abbac i,j 临时存储 {a} abbac i 临时存储 {a,b} 第二次 (临时存储内是否有j位置的元素 因为没有,所以j++,临时存储增加b) j 第一次 (检查临时存储内是否有j位置的元素 因为没有,所以j++,临时存储增加a) abbac i 临时存储 {b} 第三次 (临时存储内是否有j位置的元素 因为有b,因此i++,并且剔除i位置元素) j abbac i 临时存储 {} 第四次 (临时存储内是否有j位置的元素 因为有b,i++,剔除b) j abbac i, 临时存储 {b} 第五次 (临时存储内是否有j位置的元素 因为没有,j++,将b放入临时存储) j abbac i 临时存储 {b,a} 第六次 (临时存储内是否有j位置的元素 因为没有,j++,临时存储增加a) j abbac i 临时存储 {b,a,c} 第7次 (临时存储内是否有j位置的元素 因为没有,j++,临时存储增加c) j 最终结果取临时存储中存储内容最多的那个,因此是b,a,c

代码如下:

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字