滑动窗口的一种算法模板
滑动窗口的一种算法模板
1
2
3
4
5
6
7
8
9
|
//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
//当前考虑的元素
while (l <= r && check()) {//区间[left,right]不符合题意
//扩展左边界
}
//区间[left,right]符合题意，统计相关信息
}
|
3. 无重复字符的最长子串 - 力扣（LeetCode）
给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串
的长度。
本题套用模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int lengthOfLongestSubstring(String s) {
char[] cs = s.toCharArray();
int max = 0;
Set<Character> set = new HashSet<>();
for(int l = 0 , r = 0 ; r < cs.length ; r++){
char c = cs[r];
while(set.contains(c)){
set.remove(cs[l]);
l++;
}
set.add(c);
max = Math.max(max,r-l+1);
}
return max;
}
|
209. 长度最小的子数组 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int minLength = Integer.MAX_VALUE;
for (int l = 0, r = 0; r < nums.length; r++) {
sum += nums[r];
while (l < r && sum >= target) {
sum -= nums[l];
l++;
minLength = Math.min(minLength, r - l);
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
|