发表更新数据结构与算法 / 数组与字符串7 分钟读完 (大约1081个字)

滑动窗口法

滑动窗口是一种解题技巧，一句话说明就是维护一个窗口，不断滑动，更新答案。

滑动窗口适合的一维情况，比如数组、字符串；同时，拓展到二维也不是不可能。

根据问题求解的特性，可分为最小滑动窗口和最大滑动窗口两种解题模版。

滑动窗口大致逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 窗口由left和right共同维护，左闭右闭
int left = 0, right = 0;
while (right < 某个值） {
    // 增大窗口
    right++;
  	// 更新窗口内的性质
    window.add(s[right]);
    //当窗口内满足xx条件时，缩小窗口
    while (window needs shrink) { 
        window.remove(s[left]);
        left++;
    }
  	//更新答案
}

通过双指针维护窗口，right指针扩大窗口，left指针缩小窗口。滑动窗口射击两个过程，扩大窗口以及缩小窗口。需要注意一些细节，比如说如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。

（1）窗口内状态收集一般通过容器进行，比如map、queue（单调队列）等。

（2）两种模型

如果在扩大阶段收集答案，那么就是最大窗口模型，但注意同时要满足题目特定条件。背后的思想与贪心类似。

如果在窗口缩小阶段收集答案，那么就是最小窗口模型。

那么这两种模型到底有什么区别？滑动窗口法都有窗口扩张和窗口缩小的过程。最大窗口模型，窗口缩小是使条件满足的过程，然后收集答案；最小窗口模型，只有在满足条件时才能进行窗口缩小，窗口缩小的目的是使得条件不满足，在每一次窗口缩小过程中收集答案。

最小滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void slidingWindow(string s, string t){
  int left=0,right=0;
  int valid = 0;
  while(right<s.size()){
    //取数据
    char c = s[right];
    
		// 将数据加入窗口
    // your code here
    
    while(窗口满足条件){
      //记录结果
      // your code here
      //缩小窗口，使之不满足条件
    }
   
     //此时窗口不满足条件，继续扩大
     right++;
  }
}

可以看出来，最小滑动窗口的条件是在while循环内更新的，因为一旦满足了条件就要马上更新，取最小。

最大滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void slidingWindow(string s, string t){
  int left=0,right=0;
  int valid = 0;
  while(right<s.size()){
    //取数据
    char c = s[right];
    
		// 将数据加入窗口
    // your code here
    
    while(窗口不满足条件){
      //缩小窗口，使之满足条件
    }
     //记录结果
     // your code here
    
     //此时窗口满足条件，继续扩大
     right++;
  }
}

最大窗口的条件更新是在while外更新的。当我们的窗口满足条件时，我们希望继续扩大窗口，期望得到最大值。一旦窗口内的数据不满足条件了，我们就缩小窗口，调整满足条件。

滑动窗口法实战

字符串排列

https://leetcode.cn/problems/permutation-in-string/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length()>s2.length()) return false;
        // 初始化S1大小的窗口，然后不断向右滑动
        int[] winodw = new int[26];
        int[] s1_hash = new int[26];
        for(int i=0; i<s1.length(); ++i){
            s1_hash[s1.charAt(i)-'a'] += 1;
            winodw[s2.charAt(i)-'a'] += 1;
        }
        if(Arrays.equals(s1_hash, winodw)) return true;
        for(int i=s1.length(); i<s2.length(); ++i){
            winodw[s2.charAt(i-s1.length()) -'a']--;
            winodw[s2.charAt(i)-'a']++;
            if(Arrays.equals(s1_hash, winodw)) return true;
        }
        return false;
    }
}

很简单的思路，用哈希表映射窗口每个字母的个数，然后不断向右滑动。

字符串中的所有字母异位词

https://leetcode.cn/problems/find-all-anagrams-in-a-string/

（1）暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if (p.length() > s.length() ) return ans;
        int[] p_map = new int[26];
        int[] win_map = new int[26];
        for(int i=0; i<p.length(); ++i){
            p_map[p.charAt(i)-'a'] +=1;
            win_map[s.charAt(i)-'a'] +=1;
        }
        if (Arrays.equals(p_map, win_map)) ans.add(0); // 这里可优化
        for(int i=p.length();i<s.length(); ++i){
            win_map[s.charAt(i-p.length())-'a']--;
            win_map[s.charAt(i) -'a']++;
            if (Arrays.equals(p_map, win_map)) ans.add(i-p.length()+1);// 这里可优化
        }
        return ans;
    }
}

窗口大小固定，往右滑动。

在比较窗口内字符和p字符时，通过Arrays.equals(p_map, win_map)线性遍历每一个位置是否相同，代价太大。能否优化？

（2）优化比较

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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if (p.length() > s.length() ) return ans;
        int[] count = new int[26]; // count表示窗口内字母数量减去p的字母数量
        int diff = 0; // 表示差异的字母数量
        for(int i=0; i<p.length(); ++i){
            count[s.charAt(i)-'a'] +=1;
            count[p.charAt(i)-'a'] -=1;
        }
        for(int cnt:count){
            if(cnt!=0) diff++;
        }
        if (diff==0) ans.add(0);
        for(int i=p.length();i<s.length(); ++i){
            // 处理左端字母减少
            if(count[s.charAt(i-p.length())-'a']==1){
                diff--;
            }else if(count[s.charAt(i-p.length())-'a']==0){
                diff++;
            }
            count[s.charAt(i-p.length())-'a']--;
            // 处理右端字母增加
            if(count[s.charAt(i)-'a']==-1){
                diff--;
            }else if(count[s.charAt(i)-'a']==0){
                diff++;
            }
            count[s.charAt(i)-'a']++;
            if (diff==0) ans.add(i-p.length()+1); //比较的优化
        }
        return ans;
    }
}

为了减少比较两个数组的遍历次数，我们维护一个diff变量表示两个数组中的差异数量。当diff为零，表示两个数组一摸一样。此时，可用一个数组count作为两个数组的差值，差值为零自然两个数组相同。

当窗口滑动时，我们知道右侧字母增加，左侧字母减少。右侧字母增加时，如果此位置差值为-1，那么窗口滑动的结果是使得此位置的差值为0，那么diff减少。

在收集答案时，只需判断一次diff是否为零。

最小窗口实战

长度最小子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int windowCount = 0;
        int ans = Integer.MAX_VALUE; 
        int l =0, r=0;
        while(r<nums.length){
            windowCount += nums[r];
            while(windowCount>=target){
                ans = Math.min(ans, r-l+1);
                windowCount -= nums[l];
                l++;
            }
            r++;
        }
        return ans==Integer.MAX_VALUE?0:ans;
    }
}

最小滑动窗口入门题了，窗口内状态只需要用一个变量保存，然后在缩小窗口的过程中更新答案。

最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/

（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
class Solution {
    public boolean isCovered(int[] s1, int[] s2){
       for(int i=0; i<s1.length; ++i) {
           if(s1[i]<s2[i]) return false;
       }
       return true;
    }
    public int[] initMap(String s, int len){
        int[] ret = new int[60];
        for(int i=0; i<len; ++i){
            ret[s.charAt(i)-'A']++;
        }
        return ret;
    } 
    public String minWindow(String s, String t) {
        if(s.length()<t.length()) return "";
        int l=0, r=0, record_l=0, record_r=s.length()+1;
        int[] tmap = initMap(t, t.length()); 
        int[] window = new int[60];
        while(r<s.length()){
            window[s.charAt(r)-'A']++;
            while(isCovered(window, tmap)){ //可优化
                if(record_r-record_l > r-l){
                    record_l = l;
                    record_r = r;
                }
                window[s.charAt(l)-'A']--;
                l++;
            }
            r++;
        }
        return record_r==1+s.length()?"":s.substring(record_l, record_r+1);
    }
}

（2）比较优化

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
class Solution {
    public int[] initMap(String s, int len){
        int[] ret = new int[60];
        for(int i=0; i<len; ++i){
            ret[s.charAt(i)-'A']--;
        }
        return ret;
    } 
    public String minWindow(String s, String t) {
        if(s.length()<t.length()) return "";
        int l=0, r=0, record_l=0, record_r=s.length()+1;
        int[] window = initMap(t, t.length());  // window为窗口字母与t差值
        int cover=0; // cover为window内字母大于等于0的个数
        for(int win:window){if(win>=0) cover++;}
        while(r<s.length()){
            if(window[s.charAt(r)-'A']==-1) cover++; //1.窗口扩张
            window[s.charAt(r)-'A']++;
            while(cover==60){ //优化比较
                if(record_r-record_l > r-l){
                    record_l = l;
                    record_r = r;
                }
                if(window[s.charAt(l)-'A']==0) cover--;//2.窗口缩小
                window[s.charAt(l)-'A']--;
                l++;
            }
            r++;
        }
        return record_r==1+s.length()?"":s.substring(record_l, record_r+1);
    }
}

利用一个cover表示字母覆盖情况，那么每个位置都需要覆盖到，满足覆盖条件时cover==数组长度。

cover更新：窗口扩张，右侧位置为 -1时，cover增加；窗口缩小，左侧位置为0时，cover减小。

核心思想：维护比较的差异度！而不是每次重新比较，忽略了历史值的利用。

最大窗口实战

无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i=0,j=0,ans=0;
        Map<Character, Integer> map = new HashMap<>();
        while(j<s.length()){
            char ch = s.charAt(j);
            map.put(ch ,map.getOrDefault(ch ,0)+1);
            while(map.get(ch)>1){ //不满足条件就缩小窗口
                char d_ch = s.charAt(i);
                map.put(d_ch ,map.getOrDefault(d_ch ,0)-1);
                i++;
            }
            ans = Math.max(ans, j-i+1);  //满足条件后更新
            j++;
        }
        return ans;
    }
}

参考：

作者：labuladong
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/9749/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/

作者：HelloPGJC
链接：https://leetcode.cn/problems/fruit-into-baskets/solutions/1437444/shen-du-jie-xi-zhe-dao-ti-he-by-linzeyin-6crr/

滑动窗口法

https://xyz.desirer233.fun/2023/12/21/数据结构与算法/数组与字符串/Java滑动窗口/

作者

Desirer

发布于

2023-12-21

更新于

2024-04-15

许可协议

#

分类

×