美文网首页算法
[LeetCode OJ]- Longest Substring

[LeetCode OJ]- Longest Substring

作者: 其中一个cc | 来源:发表于2017-01-04 15:05 被阅读0次

这道题的要求是:在一个给定的字符串中查找最长的无重复字符的子串,返回这个子串的长度

一开始的思路:使用两个指针标记子串的起止位置,然后穷举出所有子串,对所有子串进行判断是否有重复字符。这个方法肯定时间上不好。

于是,考虑到以下情况时,第一个子串(ABCD)判断过后,第二个子串(ABCDEAD)可以不用每个字符都进行判断,只需判断“比第一个子串多余的”部分(EAD)的字符,这样就可以减少比较次数。

这里用到一个sliding window(滑动窗口)的东西,就是一个可以伸缩的区间[i,j)

起止位置用i,j表示;最大字符长度用ans表示;查询过程中的最长字符用一个set存放。

相关文章

网友评论

    本文标题:[LeetCode OJ]- Longest Substring

    本文链接:https://www.haomeiwen.com/subject/elwovttx.html