模板:
//外层循环扩展右边界,内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {//当前考虑的元素while (l <= r && check()) {//区间[left,right]不符合题意//扩展左边界}//区间[left,right]符合题意,统计相关信息
}
无重复字符的最长字串问题
class Solution{pubilc int lengthOfLongestSubstring(String s){char[] ss = s.toCharArray();//将字符串转变为数组Set<Character> set = new HashSet<>();//使用Character进行去重操作int max = 0;//设置一个初始最大值for(int left = 0 , right = 0 ; right < s.length() ; right++){//设置左右窗口边界,初始都在0号索引的位置,right不断向右侧++;char ch = ss[right];//取值赋给chwhile(set.contains(ch)){//将ch和HashSet里面的数作比较,如果有重复就做下面的操作set.remove(ss[left]);//移除最左侧的数;left++;//并将左侧窗口++缩小窗口的范围}set.add(ss[right]);//将最右侧新的数值压入栈max = Math.max(max , rifht - left +1);//最大值进行比对}return max;//返回最大值}
}
在这里我对每一步都做了详细的解释,最开始让我疑惑的地方是
while(set.contains(ch)){//将ch和HashSet里面的数作比较,如果有重复就做下面的操作
set.remove(ss[left]);//移除最左侧的数;
left++;//并将左侧窗口++缩小窗口的范围
}
这段代码最开始让我想如果里面有很多重复的代码怎么办,后面反应过来这个ch的数在这个时候并没有被压入到栈里面,所以如果有重复的就会一直执行while循环,left一直++,知道没有重复的才压入到栈中,最终返回答案。