求最大无重复字符的子串

思路:用一个map记录各个字符的下标,首先将所有的下标初始化为-1,然后向后遍历的过程中记录当前字符的下标,并将当前字符的下标与上一个相同字符的下标做差值,即可得到它们之间无重复字符的子串。然后用Max记录更新最大子串数,并更新map存储的下标值,即从这个重复值重新开始数字符串的数(最大无重复字符子串必定在两个重复字符之间,或者是整个字符串的长度)

这种方法好像被叫做滑动窗口法

"滑动窗口"

比方说 abcabccc 当你右边扫描到abca的时候你得把第一个a删掉得到bca,

然后"窗口"继续向右滑动,每当加到一个新char的时候,左边检查有无重复的char,

然后如果没有重复的就正常添加,

有重复的话就左边扔掉一部分(从最左到重复char这段扔掉),在这个过程中记录最大窗口长度

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容