Posted Updated Leetcode9 minutes read (About 1314 words)0 visits

Sliding Window总结

Sliding Window

sliding window问题的思想并不复杂，就是设立一个start和一个end指针进行遍历，end不停地在前进，start只有在条件不符合的时候前进，但是在进行过程中由于变量的更改会出现有思路写不出来的问题，所以总结一下模板。

sliding window思路：

1
2
3
4
5
while(end<length){
    1. 处理end位置的character，end++
    2. 如果达到了某种条件，我们使用while loop或者if打破这种条件，start++
    3. 更新结果，这个时候的end是还没处理过的，start是处理过的，所以如果求长度什么的是end-start而不是end-start+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
39
40
41
42
43
44
45
46
47
48
public class Solution {
    public List<Integer> slidingWindowTemplateByHarryChaoyangHe(String s, String t) {
        //init a collection or int value to save the result according the question.
        List<Integer> result = new LinkedList<>();
        if(t.length()> s.length()) return result;
        
        //create a hashmap to save the Characters of the target substring.
        //(K, V) = (Character, Frequence of the Characters)
        Map<Character, Integer> map = new HashMap<>();
        for(char c : t.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        //maintain a counter to check whether match the target string.
        int counter = map.size();//must be the map size, NOT the string size because the char may be duplicate.
        
        //Two Pointers: begin - left pointer of the window; end - right pointer of the window
        int begin = 0, end = 0;
        
        //the length of the substring which match the target string.
        int len = Integer.MAX_VALUE; 
        
        //loop at the begining of the source string
        while(end < s.length()){
            
            char c = s.charAt(end);//get a character
            
            if( map.containsKey(c) ){
                map.put(c, map.get(c)-1);// plus or minus one
                if(map.get(c) == 0) counter--;//modify the counter according the requirement(different condition).
            }
            end++;
            
            //increase begin pointer to make it invalid/valid again
            while(counter == 0 /* counter condition. different question may have different condition */){
                
                char tempc = s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointer
                if(map.containsKey(tempc)){
                    map.put(tempc, map.get(tempc) + 1);//plus or minus one
                    if(map.get(tempc) > 0) counter++;//modify the counter according the requirement(different condition).
                }
                begin++;
            }
            /* save / update(min/max) the result if find a target*/
            // result collections or result int value
        }
        return result;
    }
}
  1. Longest Substring Without Repeating Characters: 这道题是可以使用我们的模板，也就是使用map记录出现的次数，如果次数大于1，代表不合乎条件，那么start进行运动。
    一个优化方式是我们直接存储上一次遇到这个character的位置，这样我们使用start更新的时候可以一步到位，不用进行loop
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
//模板写法
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int start = 0;
        int end = 0;
        int counter = 0;
        int ans = 0;
        while(end<s.length()){
            char c = s.charAt(end);
            map.put(c, map.getOrDefault(c, 0)+1);
            if(map.get(c)>1){
                counter++;
            }
            end++;
            while(counter>0){//no repeat就是counter必须为零的意思
                char temp = s.charAt(start);
                map.put(temp, map.get(temp)-1);
                if(map.get(temp)==1){
                    counter--;
                }
                start++;
            }
            ans = Math.max(ans, end-start);
        }
        
        return ans;
    }
}
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) {
        if(s.length()==0){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int start = 0;
        int end = 0;
        int ans = 0;
        while(end<=s.length()-1){
            char c = s.charAt(end);
            if(map.containsKey(c)){//当条件不成立的时候，就是我们使用start的时候
                start = Math.max(start, map.get(c)+1);
            }  
            map.put(c, end);
            ans = Math.max(ans, end-start+1);
            end++;
        }
        return ans;
    }
}
  1. Longest Substring with At Most Two Distinct Characters+340. Longest Substring with At Most K Distinct Characters: 套用我们的模板即可，counter一开始为零，每当我们的end遇到在map中不存在的character的时候，我们的count++；如果counter>k，说明我们现在有超过k中character，所以我们移动start直到某一个character在map中size为零，counter–。
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
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        int start = 0;
        int end = 0;
        int counter = 0;//map中数量大于0的character
        while(end<=s.length()-1){
            char c = s.charAt(end);
            map.put(c, map.getOrDefault(c, 0)+1);
            if(map.get(c)==1){//如果某个character的数量为1，说明是我们新加进去的，也就是map中数量大于0的元素加一
                counter++;
            }
            end++;
            while(counter>k){
                char temp = s.charAt(start);
                map.put(temp, map.get(temp)-1);
                if(map.get(temp)==0){
                    counter--;
                }
                start++;
            }
            res = Math.max(res, end-start);
        }
        return res;
    }
}
  1. Minimum Window Substring: 求最小与求最大是类似的镜像问题，他们进行结果更新的地方不一样。
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
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for(char c: t.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        
        int minLength = Integer.MAX_VALUE;
        int minStart = 0;
        int minEnd = 0;
        int start = 0;
        int end = 0;
        int counter = map.size();
        
        while(end<s.length()){
            char c = s.charAt(end);
            if(map.containsKey(c)){
                map.put(c, map.get(c)-1);
                if(map.get(c)==0){
                    counter--;
                }
            }
            end++;
            
            while(counter==0){
                char temp = s.charAt(start);
                if(minLength>end-start){//求最小的substring，符合条件的在while loop里面，求最长的substring，符合条件的在外面
                    minStart = start;
                    minEnd = end;
                    minLength = end-start;
                }
                if(map.containsKey(temp)){
                    map.put(temp, map.get(temp)+1);
                    if(map.get(temp)>0){
                        counter++;
                    }
                }
                start++;
            }
        }
        
        return minLength==Integer.MAX_VALUE?"":s.substring(minStart, minEnd);
    }
}

K different element题目：
这种题目可以转换成我们之前做过的At Most K类型题，Exactly(K) = AtMost(K) - AtMost(K-1)

  1. Subarrays with K Different Integers
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
/*
992. Subarrays with K Different Integers
Hard

521

11

Favorite

Share
Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

 

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
*/

class Solution {
    public int subarraysWithKDistinct(int[] A, int K) {
        return atMostK(A, K)-atMostK(A, K-1);
    }
    
    private int atMostK(int[] A, int K){
        int start = 0;
        int end = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        int ans = 0;
        while(end<=A.length-1){
            int num = A[end];
            if(map.getOrDefault(num, 0)==0){
                count++;
            }
            map.put(num, map.getOrDefault(num, 0)+1);
            end++;
            while(count>K){
                int startNum = A[start];
                map.put(startNum, map.get(startNum)-1);
                if(map.get(startNum)==0){
                    count--;
                }
                start++;
            }
            ans = ans + end - start;//the total number of subarrays ending at j that contain at most K distinct.
            
        }
        
        return ans;
    }
}
  1. Count Number of Nice Subarrays
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
/*
1248. Count Number of Nice Subarrays
Medium

56

0

Favorite

Share
Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

 

Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.
Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
 

Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length
*/
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k-1);
    }
    
    private int atMostK(int[] nums, int k){
        int start = 0;
        int end = 0;
        int count = 0;
        int ans = 0;
        while(end<=nums.length-1){
            if(nums[end]%2==1){
                count++;
            }
            end++;
            while(count>k){
                if(nums[start]%2==1){
                    count--;
                }
                start++;
            }
            ans = ans + end -start;
        }
        return ans;
    }
}
Follow

Catalogue

×