滑动窗口算法
今天刷力扣题目，刷到了一个滑动窗口算法问题，这类算法问题之前没有遇到过，特此记录下来
解题思路
1.首先确定窗口的定义（比如子串的每个字符存在个数/子数组的和）
2.开始创建变量
2.1.window(HashMap/int)用来定义窗口。
2.2.left right指针[left, right)区间就是我们的窗口。
2.3结果res，需根据题意
3.window更新窗口值后,right++。到达窗口收缩条件，更新结果（如果满足题)，window更新窗口值，left–
例题
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
1
2
3
| 输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
1
2
3
4
| 输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
1
2
3
4
| 输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
解题办法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int res = 0;
while(right < s.length()){
char c1 = s.charAt(right);
window.put(c1, window.getOrDefault(c1, 0) + 1);
right++;
while(window.get(c1) > 1){
char c2 = s.charAt(left);
window.put(c2, window.getOrDefault(c2, 0) - 1);
left++;
}
res = Math.max(res, right - left);
}
return res;
}
}
|
