- 基础算法 - 滑动窗口
- 相关题目
- 3. 无重复字符的最长子串 - 力扣（LeetCode）
- 76. 最小覆盖子串 - 力扣（LeetCode）
- 567. 字符串的排列 - 力扣（LeetCode）
- 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
- 239. 滑动窗口最大值 - 力扣（LeetCode）
基础算法 - 滑动窗口
滑动窗口（Sliding Window）是一种高效的数组/字符串处理技术，常用于解决子数组或子字符串相关的问题。它通过在数组或字符串上维护一个固定大小的窗口或动态调整窗口的大小，来逐步遍历并处理每个子集。
滑动窗口的主要特点包括：
- 固定窗口大小：在某些问题中，滑动窗口的大小是固定的，窗口从数组或字符串的一端滑动到另一端。
- 动态调整窗口大小：在其他问题中，滑动窗口的大小是动态调整的，根据条件扩展或缩小窗口。
- 高效处理子问题：滑动窗口技术通过在遍历过程中维护窗口状态，能够高效地解决许多子数组或子字符串问题。
滑动窗口通常用于解决以下类型的问题：
- 最大/最小子数组和问题：寻找具有最大或最小和的子数组。
- 子字符串问题：寻找包含某些字符或满足某些条件的最长或最短子字符串。
- 计数问题：统计子数组或子字符串中满足特定条件的元素数量。
滑动窗口的实现步骤
- 初始化窗口的起始和结束位置：通常设置两个指针，分别表示窗口的起始和结束位置。
- 滑动窗口：根据问题的需求移动窗口的起始或结束位置，动态调整窗口大小。
- 更新状态：在滑动窗口的过程中，维护并更新窗口内的状态（如窗口内元素的和、计数等）。
- 处理结果：在滑动窗口的过程中或结束后，根据窗口内的状态处理最终结果。
滑动窗口是一种非常强大的技术，能够将许多原本需要嵌套循环解决的问题简化为线性时间复杂度，是解决大量数据处理问题的重要工具。
相关题目
难度：中等
一开始我写出来的解法如下，用到了哈希表和滑动窗口。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0;
int start = 0;
int cur = start;
int len = s.length();
HashSet<Character> set = new HashSet<Character>();
while(cur<len){
char a = s.charAt(cur);
if(set.contains(a)){
start ++;
cur = start;
set.clear();
}else{
set.add(a);
cur++;
int tmp = cur - start;
if(res < tmp) res = tmp;
}
}
return res;
}
}
|
我们的滑动窗口一旦遇到重复的，就会从下一个字母从头开始数，其实浪费了非常多的时间和资源。
所以这样的时间复杂度很高。
要优化，就要优化头部和尾部的滑动时机。
队列式滑动窗口，比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public int lengthOfLongestSubstring(String s){
int res = 0;
int len = s.length();
HashSet<Character> map = new HashSet<Character>();
int left = 0;
int right = left;
while(right<len){
char cur = s.charAt(right);
if(!map.contains(cur)){
map.add(cur);
right++;
int tmp = right - left;
if(res < tmp) res = tmp;
}else{
do{
char head_char = s.charAt(left);
map.remove(head_char);
left++;
}while(map.contains(cur));
}
}
return res;
}
}
|
难度：困难
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| class Solution {
public String minWindow(String s, String t) {
int s_len = s.length();
int t_len = t.length();
int start = 0;
int len = Integer.MAX_VALUE;
int[] cnt = new int[128];
int count = 0;
for (int i = 0; i < t_len; i++) {
char tmp = t.charAt(i);
cnt[tmp]++;
count++;
}
int right = 0;
int left = 0;
while (right < s_len) {
char tmp = s.charAt(right);
right++;
cnt[tmp]--;
if (cnt[tmp] >= 0) {
count--;
}
while (count == 0) {
char tmp_ = s.charAt(left);
cnt[tmp_]++;
if (cnt[tmp_] > 0) {
int len_tmp = right - left;
if (len_tmp < len) {
len = len_tmp;
start = left;
}
count++;
}
left++;
}
}
if (len == Integer.MAX_VALUE)
return "";
else
return s.substring(start, start + len);
}
}
|
要注意窗口移动的细节。
难度：中等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public boolean checkInclusion(String s1, String s2) {
int len_1 = s1.length();
int len_2 = s2.length();
int[] need = new int[128];
int count = 0;
for(int i=0;i<len_1;i++){
char tmp = s1.charAt(i);
need[tmp]++;
count++;
}
int left = 0;
int right = 0;
while(right<len_2){
char tmp = s2.charAt(right);
right++;
need[tmp]--;
if(need[tmp]>=0){
count--;
}
while(count==0){
char tmp_ = s2.charAt(left);
need[tmp_]++;
if(need[tmp_]>0){
count++;
if(len_1==(right-left))
return true;
}
left++;
}
}
return false;
}
}
|
和上一题是几乎一样的，不同点在于此题需要判断滑动窗口中的串是不是子串的排列之一，通过滑动窗口的长度判断即可。
难度：中等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<Integer>();
int s_len = s.length();
int p_len = p.length();
int[] need = new int[128];
int count = 0;
for(int i=0;i<p_len;i++){
char tmp = p.charAt(i);
need[tmp]++;
count++;
}
int left=0;
int right=0;
while(right<s_len){
char tmp = s.charAt(right);
right++;
need[tmp]--;
if(need[tmp]>=0){
count--;
}
while(count==0){
char tmp_ = s.charAt(left);
need[tmp_]++;
if(need[tmp_]>0){
count++;
if((right-left)==p_len)
res.add(left);
}
left++;
}
}
return res;
}
}
|
76 567 438 这三个题都可以使用同一个模板去解决。
难度：困难
最暴力解法如下，时间复杂度为(n*m)，必然会超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
int[] res = new int[len-k+1];
for(int i=0;i<len-k+1;i++){
int tmp_max = Integer.MIN_VALUE;
for(int j=i;j<i+k;j++){
tmp_max=Math.max(nums[j],tmp_max);
}
res[i] = tmp_max;
}
return res;
}
}
|
那么有没有什么可以减少时间复杂度的呢？
在暴力法中，获得新区间的最大值的方法是重新遍历一遍新区间，这使得时间复杂度变得高了，每一次寻找最大值的时间复杂度为O(k)
要降低复杂度，主要是： 在每次滑动窗口后，如何用O(1)的时间复杂度获取最大值
我们可以使用单调队列的方式来解决。
维护一个队列：使得这个队列中的元素全是当前窗口的元素，并且这些元素是单调递减的（队列头是最大的，依次递减）
每一个新的滑动窗口，只需要获取队列头的值就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int len = nums.length;
int[] res = new int[len - k + 1];
LinkedList<Integer> queue = new LinkedList<>();
for (int r = 0; r < len; r++) {
int l = r - k + 1;
if (!queue.isEmpty() && queue.peekFirst() < l) {
queue.removeFirst();
}
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[r]) {
queue.removeLast();
}
queue.addLast(r);
if (l >= 0) {
res[l] = nums[queue.peekFirst()];
}
}
return res;
}
}
|
