Sliding Window算法通用总结

Posted on |

本文主要针对Sliding Window类型的算法进行总结归纳解题模板，适用于大部分解决字符串子问题的算法。这里将列举一下比较有代表性的，在每个解题的代码中都标注了一些具体的模版规则。

Sliding Window Template（解题模板）

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
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
public class Solution {
    public List<Integer> slidingWindowTemplate(String s, String t) {
        //初始化返回的结果集
        List<Integer> result = new LinkedList<>();
        if(t.length()> s.length()) return result;
        
        //通过hashmap存储目标子串的所有字符
        //(K, V) = (Character, 字符出现的次数/频率)
        Map<Character, Integer> map = new HashMap<>();
        for(char c : t.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        //维护一个标志位，标记当前窗口(begin,end)是否包含hashmap中目标子串
        int counter = map.size();//一定要是map的长度，因为可能会有重复字符
        
        //双指针，一个开头一个结尾
        int begin = 0, end = 0;
        
        //辅助判断条件.
        int len = Integer.MAX_VALUE; 
        
        //开始循环sliding window 移动end右窗口的位置
        while(end < s.length()){
            
            char c = s.charAt(end);//获取一个字符
            
            if( map.containsKey(c) ){
                map.put(c, map.get(c)-1);//减少key对应value的值
                if(map.get(c) == 0) counter--;//如果hashmap中的key的value全部消耗完，减少counter
            }
            end++;
            
            //当counter标志位符合要求的时候 移动begin左窗口的位置
            while(counter == 0 /* counter condition. different question may have different condition */){
                
                char tempc = s.charAt(begin);//选择左窗口begin当前位置的字符
                if(map.containsKey(tempc)){
                    map.put(tempc, map.get(tempc) + 1);//如果当前的begin所在的字符在map中存在，更新对应key位置value+1
                    if(map.get(tempc) > 0) counter++;//如果当前map中的key对应value大于0，counter标志位增加，跳出循环，让end继续往后滑
                }
                
                //判断当前的窗口是否满足其他条件，不同的问题主要是这里不同
                //如果是最小子串，那么判断当前的窗口是否更小 存下更小的
                //如果是包含子串的列表 那么保存每个窗口
           
                begin++;
            }
        }
        return result;
    }
}

P438. Find All Anagrams in a String

问题描述（难度中等）

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

解题代码

利用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
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
54
55
56
57
package P438;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * using slide window
 */
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int begin=0;
        int end=0;
        List<Integer> result=new ArrayList<>();
        //构造子串的map
        Map<Character,Integer> pMap=new HashMap<>(128,0.75f);
        for (int i = 0; i < p.length(); i++) {
            pMap.put(p.charAt(i),pMap.getOrDefault(p.charAt(i),0)+1);
        }
        int count=pMap.size();
        while (end<s.length()){
            Character currentChar=s.charAt(end);
            //如果当前key在pMap中
            if (pMap.containsKey(currentChar)) {
                //pMap值-1
                pMap.put(currentChar,pMap.get(currentChar)-1);
                //当前key全部减完 count更新
                if (pMap.get(currentChar)==0) {
                    count--;
                }
            }
            end++;
            //如果count目标减为0 从begin开始加回去
            while (count==0) {
                Character c=s.charAt(begin);
                if (pMap.containsKey(c)) {
                    pMap.put(c,pMap.get(c)+1);
                    if (pMap.get(c)>0) {
                        count++;
                    }
                }
                //记录当前的begin的位置之后继续遍历
                //这里可以判断下当前是否满足条件
                if ((end-begin)==p.length()) {
                    result.add(begin);
                }
                begin++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        new Solution().findAnagrams("cbaebabacd","abc");
    }
}

P76. Minimum Window Substring

####问题描述（难度偏难）

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

1
2
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

解题代码

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
54
55
56
57
package P76;

import java.util.HashMap;
import java.util.Map;

/**
 * sliding window
 */
class Solution {
    public String minWindow(String s, String t) {
        //定义sliding begin位置 end位置 结束标记counter计数器
        int begin=0,end=0,counter;
        Integer len=s.length();
        String target="";
        Map<Character,Integer> tMap=new HashMap<>(129,0.75f);

        for (int i = 0; i < t.length(); i++) {
            tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i),0)+1);
        }
        counter=tMap.size();
        //开始主循环
        while (end<s.length()){
            //判断当前的end位置是否在tmap中存在
            if (tMap.containsKey(s.charAt(end))) {
                //如果存在的话就从tmap中踢掉一个
                tMap.put(s.charAt(end),tMap.get(s.charAt(end))-1);
                //如果当前位置减掉之后变成零了 就更新counter计数器
                if (tMap.get(s.charAt(end))==0) {
                    counter--;
                }
            }
            //继续执行遍历哟
            end++;
            //每次都可以判断下counter是否等于零 等于0的话说明当前的begin和end位置是符合条件的（t中所有元素在当前窗口都存在）
            //确定到这个窗口之后，需要将begin往前推，也就是窗口继续向前滑动
            while (counter==0){
                if (tMap.containsKey(s.charAt(begin))) {
                    tMap.put(s.charAt(begin),tMap.get(s.charAt(begin))+1);
                    if (tMap.get(s.charAt(begin))>0) {
                        counter++;
                    }
                }
                //判断下当前的窗口是否满足条件，这里的话只需要满足完全存在的条件也就是如果当前窗口定位到的是abcde 但是目标窗口是abe也可以返回
                if (end-begin<=len) {
                    len=end-begin;
                    target=s.substring(begin,end);
                }
                begin++;
            }
        }
        return target;
    }

    public static void main(String[] args) {
        new Solution().minWindow("ADOBECODEBANC","ABC");
    }
}

P30. Substring with Concatenation of All Words

问题描述（难度偏难）

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

1
2
3
4
5
6
Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

1
2
3
4
Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

解题代码

这道题关键点是words的数组中单词的长度是一致的，实际上演变为sliding window的变型，时间复杂度依旧是O(N)。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package P30;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * sliding window template
 * 时间复杂度O(N)
 * 空间复杂度O(N)
 */
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        //定义存结果的list
        List<Integer> result=new ArrayList<>();
        if (s==null || s.length()==0 || words==null || words.length==0) {
            return result;
        }
        //定义位置 起点 终点 每次跳动的距离 定义一个counter标志
        int begin=0,end=0,step=words[0].length(),counter;
        //将word的列表存到map中
        Map<String,Integer> wordsMap=new HashMap<>();
        for (String word : words) {
            wordsMap.put(word,wordsMap.getOrDefault(word,0)+1);
        }
        //设置counter默认值
        counter=wordsMap.size();
        //sliding template 循环
        for (int i = 0; i < step; i++) {
            begin=i;end=i;
            while (end+step<=s.length()){
                String curString=s.substring(end,end+step);
                if (wordsMap.containsKey(curString)) {
                    wordsMap.put(curString,wordsMap.get(curString)-1);
                    if (wordsMap.get(curString)==0) {
                        counter--;
                    }
                }
                end+=step;
                while (counter==0){
                    String beginS=s.substring(begin,begin+step);
                    if (wordsMap.containsKey(beginS)) {
                        wordsMap.put(beginS,wordsMap.get(beginS)+1);
                        if (wordsMap.get(beginS)>0) {
                            counter++;
                        }
                    }
                    //满足条件的存下来
                    if (end-begin==step*words.length) {
                        result.add(begin);
                    }
                    begin+=step;
                }
            }
            wordsMap.clear();
            for (String word : words) {
                wordsMap.put(word,wordsMap.getOrDefault(word,0)+1);
            }
            counter=wordsMap.size();
        }

        return result;
    }

    public static void main(String[] args) {
        String[] words={"ab","ba","ba"};
        String s="ababaab";
        new Solution().findSubstring(s,words);
    }
}

P567. Permutation in String

####问题描述（难度中等）

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

1
2
3
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

1
2
Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

  1. The input strings only contain lower case letters.
  2. The length of both given strings is in range [1, 10,000].

解题代码

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
54
55
56
57
58
59
package P567;

import java.util.HashMap;
import java.util.Map;

/**
 * sliding window
 * begin和end中间的部分为窗口 注意不包括begin和end
 */
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //定义前后窗口
        int begin=0,end=0,counter;
        if (s1==null) {
            return true;
        }
        if (s2==null || s1.length()>s2.length()) {
            return false;
        }
        //将s1字符存到map
        Map<Character,Integer> sMap=new HashMap<>(s1.length()*2,0.75f);
        for (int i = 0; i < s1.length(); i++) {
            char charC=s1.charAt(i);
            sMap.put(charC,sMap.getOrDefault(charC,0)+1);
        }
        counter=sMap.size();
        //开始循环
        while (end<s2.length()){
            char endChar=s2.charAt(end);
            if (sMap.containsKey(endChar)) {
                sMap.put(endChar,sMap.get(endChar)-1);
                if (sMap.get(s2.charAt(end))==0) {
                    counter--;
                }
            }
            end++;
            while (counter==0){
                char beginChar=s2.charAt(begin);
                if (sMap.containsKey(beginChar)) {
                    sMap.put(beginChar,sMap.get(beginChar)+1);
                    if (sMap.get(beginChar)>0) {
                        counter++;
                    }
                }
                //判断满足条件返回
                if ((end-begin)==s1.length()) {
                    return true;
                }
                begin++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().checkInclusion("ab","eidbaooo"));
        System.out.println(new Solution().checkInclusion("ab","eeidboaoo"));
    }
}

P424. Longest Repeating Character Replacement

####问题描述（难度中等）

Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.

In one operation, you can choose any character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.

Note:
Both the string’s length and k will not exceed 104.

Example 1:

1
2
3
4
5
6
7
8
Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

1
2
3
4
5
6
7
8
9
Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

解题代码

方法一：HashMap(N^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
35
36
37
package P424;

import java.util.*;

class Solution {
    public int characterReplacement(String s, int k) {
        //定义滑动窗口左窗口和右窗口
        int begin=0,end=0;
        //定义一个hashmap用于存储滑动窗口中的key value统计值
        Map<Character,Integer> countMap=new HashMap<>();
        //定义返回的最大值
        int maxResult=0;
        //开始循环右窗口
        while (end<s.length()){
            countMap.put(s.charAt(end),countMap.getOrDefault(s.charAt(end),0)+1);
            end++;
            //如果当前的窗口已经超出了满足条件的返回 也就是maxCount+k>end-begin
            while ((end-begin)-getMax(countMap)>k){
                char begingChar=s.charAt(begin);
                countMap.put(begingChar,countMap.get(begingChar)-1);
                begin++;
            }
            maxResult=end-begin>maxResult?end-begin:maxResult;
        }
        return maxResult;
    }
    public int getMax(Map<Character,Integer> map){
        int max=0;
        for (Integer value : map.values()) {
            max=value>max?value:max;
        }
        return max;
    }
    public static void main(String[] args) {
        new Solution().characterReplacement("AABABBA",1);
    }
}
方法二：一遍遍历(N)

方法一中我们每次都要找到当前窗口出现频率最多的key，以此来判断当前窗口是否满足条件，实际上我们不需要每次都去找到当前窗口出现频率最多的key，而只需要记录当前end索引对应的字符加入后最大频率的字母是否改变，改变了就重置最大频率。这样即使我们当前窗口最大频率不是最准确的，但是窗口永远不会大于最大频率+k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int characterReplacement(String s, int k) {
        int len = s.length();
        int[] count = new int[26];
        int start = 0, maxCount = 0, maxLength = 0;
        for (int end = 0; end < len; end++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
            while (end - start + 1 - maxCount > k) {
                count[s.charAt(start) - 'A']--;
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }
        return maxLength;
    }
}

总结

主要总结下Sliding Window的模板。