refer doc
leetcode对应题目:
解题模板:
//外层循环扩展右边界,内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
//当前考虑的元素
while (l <= r && check()) {
//扩展左边界
//触发条件,改变滑动窗口左侧边界
}
//区间[left,right]符合题意,统计相关信息
// 统计单个窗口信息,并进行相关操作
}
模板理解与扩展
- 左右指针 l r
- for遍历循环内嵌套while循环
- 满足while判断条件则变更左边界
- 每次循环统计滑动窗口
无重复最长子串模板扩展示例
public int lengthOfLongestSubstring(String s) {
//滑动窗口
char[] ss = s.toCharArray();
Set<Character> set = new HashSet<>();//去重
int res = 0;//结果
for(int left = 0, right = 0; right < s.length(); right++) {//每一轮右端点都扩一个。
char ch = ss[right];//right指向的元素,也是当前要考虑的元素
while(set.contains(ch)) {//set中有ch,则缩短左边界,同时从set集合出元素.去掉模板的l<=r,不符合题意
set.remove(ss[left]);
left++;
}
set.add(ss[right]);//别忘。将当前元素加入。
res = Math.max(res, right - left + 1);//计算当前不重复子串的长度。
}
return res;
}
标签:right,int,while,笔记,算法,set,滑动,模板
From: https://www.cnblogs.com/alidata/p/18403951