社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
在阅读的过程中有任何问题，欢迎一起交流
QQ：1494713801
题目：输入是一个字符串，找出没有重复字符的最长子字符串的长度
示例：
“abcabcbb”最长子串（abc）长度为3
“bbbbbbb”最长子串（b）长度为1
“abdevbac”最长子串（bdev）长度4
算法思想：
设置两个下标标识，初始时都位于数组的头部，并设置一个HashSet。标识runner先往后走，并将经过的字符放入HashSet中，当存在重复的字符时停止移动；此时，标识walker在后面追，直到walker的字符和runner的字符相同为止，此时walker与runner之间的字符是无重复的字符串，将长度记录为max。进行一遍遍历后可以得到最长字符串的长度值。
时间复杂度：
两个标识需要分别遍历一遍，即2*N，故复杂度为：O(n）
代码实现：
public int lengthOfLongestSubstring(String s) {
if(s==null || s.length()==0)
return 0;
HashSet<Character> set = new HashSet<Character>();
int max = 0;
int walker = 0;
int runner = 0;
while(runner<s.length())
{
if(set.contains(s.charAt(runner)))
{
while(s.charAt(walker)!=s.charAt(runner))
{
set.remove(s.charAt(walker));
walker++;
}
if(max<runner-walker)
{
max = runner-walker;
}
walker++;
}
else
{
set.add(s.charAt(runner));
}
runner++;
}
max = Math.max(max,runner-walker);
return max;
}
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
