最长无重复字符的子串
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例:
给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。
给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。
给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串,"pwke" 是 子序列 而不是子串。
实现思路
初始化hashSet
设定左指针left和右指针right,right从左向右遍历
判断元素在hashSet容器是否存在,如果不存在,则将元素放在容器中,并且计算length的大小,和max比较取最大值
如果已经存在,则从将left指针移到当前元素,并且将该元素左边的全部元素移除
重复上面的判断,直到全部遍历
总体有种类似滑窗的设计思想,有左右两个手柄,一个先滑动,当遇到和之前相同的XX,后一个也移到此位置,想起让子弹飞的一句,他跑我就追~
具体实现
public class Solution {
@Test
public void testSubStr(){
System.out.println(maxSubstring("12334"));
}
public int maxSubstring(String s) {
int n = s.length();//数组大小
Set<Character> set = new HashSet<>();
int max = 0, left= 0, right = 0;
while (left< n && right < n) {
if (!set.contains(s.charAt(left))){//判断set集合中是否存在
set.add(s.charAt(right++));//加到集合中
max = Math.max(max, right - left);//取区间大的
}
else {
set.remove(s.charAt(left++));//注意当出现重复元素的时候,该元素左边的数据全部移除,并且将left移到当前的元素位置。
}
}
return max;
}
}