LeeCode3:无重复字符的最长子串
程序员文章站
2022-07-12 12:16:10
...
题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
解析
1.暴力法
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0){
return 0;
}
char[] ss = s.toCharArray();
int len = ss.length;
Set<Character> set = new HashSet<Character>();
int max_len = 0;
//for循坏依次从头开始找
for(int i=0;i<len;i++){
//清空set
set.clear();
//后面没有最优解
if(len-i<max_len){
break;
}
//存入map
set.add(ss[i]);
int temp_len = 1;
int j = i+1;
while(j<len&&!set.contains(ss[j])){
set.add(ss[j]);
temp_len++;
j++;
}
//保存最大值
if(temp_len>max_len){
max_len=temp_len;
}
if(j==len){
break;
}
}
return max_len;
}
2.滑动窗口
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0){
return 0;
}
char[] ss = s.toCharArray();
int len = ss.length;
Set<Character> set = new HashSet<Character>();
int max_len = 0;
//滑动窗口
int i=0;
int j=0;
while(j<len){
if(!set.contains(ss[j])){
//不在set中
set.add(ss[j]);
max_len = Math.max(set.size(), max_len);
j++;
}else{
//在set中
set.remove(ss[i]);
i++;
}
}
return max_len;
}
上一篇: 贪心算法--牛客倒水
下一篇: Java中类的继承学习小结