rhb_blog

rao的博客

0%

Algorithm__滑动窗口

发表于 更新于 分类于 ，

滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”，“连续子数组 xxxx”，就应该可以想到滑动窗口。能不能解决另说，但是这种敏感性还是要有的。

从类型上说主要有：

  • 固定窗口大小
  • 窗口大小不固定，求解最大的满足条件的窗口
  • 窗口大小不固定，求解最小的满足条件的窗口（上面的 209 题就属于这种）

后面两种我们统称为可变窗口。当然不管是哪种类型基本的思路都是一样的，不一样的仅仅是代码细节。

固定窗口大小

对于固定窗口，我们只需要固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点，并且保证：

  1. l 初始化为 0
  2. 初始化 r，使得 r - l + 1 等于窗口大小
  3. 同时移动 l 和 r
  4. 判断窗口内的连续元素是否满足题目限定的条件
    • 4.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解
    • 4.2 如果不满足，则继续。

可变窗口大小

对于可变窗口，我们同样固定初始化左右指针 l 和 r，分别表示的窗口的左右顶点。后面有所不同，我们需要保证：

  1. l 和 r 都初始化为 0
  2. r 指针移动一步
  3. 判断窗口内的连续元素是否满足题目限定的条件
    • 3.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行 3.1
    • 3.2 如果不满足，则继续。

形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。

Leetcode 3.无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int r = 0;
        int l = 0;
        int max =0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for(r = 0;r<s.length();r++)//右边的窗口是一直往前走的
        {
            if(map.containsKey(s.charAt(r)))//当不符合条件时，左边窗口移动
                l = Math.max(l,map.get(s.charAt(r)) + 1);//只有右边加进窗口的元素是重复的，左边才会移动，所以要移动到重复元素后面一位
            map.put(s.charAt(r),r);
            max = Math.max(max,r-l+1);
        }
        return max;
        }
    }

Leetcode 76.最小覆盖子串

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 String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        int t_length=t.length();
        char[] chars = s.toCharArray(), chart = t.toCharArray();
        int[] hold = new int[128];//记录窗口中的元素和其个数
        //记录t中的所有元素和元素出现的个数
        for(int i = 0;i<t_length;i++)
        {
            char temp=chart[i];
            hold[temp]--;
        }
        String output="";
        int right=0;
        int left=0;
        int count=0;//窗口中含有t字符串的元素个数
        for(right=0;right<s.length();right++)
        {
            hold[chars[right]]++;
            if(hold[chars[right]]<=0)count++;//表示右边框进来的是t中的元素
            //当窗口元素达到要求后，此时的目标是找到最小的窗口
            //情况一：左边的元素是不需要的，直接进行左窗口移位
            //情况二：左边的元素是需要的，但是此时右边寻找到了一样的元素，为了进行最小窗口的迭代，将左窗口移位
            while(count==t_length&&hold[chars[left]]>0)
            {
                hold[chars[left]]--;
                left++;
            }
            //进行最小子串的迭代
            if(count==t_length)
            if(output==""||output.length()>right-left+1)
                output=s.substring(left,right+1);
        }
        return output;
    }
}

Leetcode 209.长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int right=0;
        int left=0;
        int num=0;//记录子数组和
        int count=0;//记录子数组个数
        for(right=0;right<nums.length;right++)
        {
            num+=nums[right];
            while(num>=target)
            {
                //最小子数组迭代
                if(count==0||count>right-left+1)
                    count=right-left+1;
                //在满足要求的基础上寻找最小子数组
                //此时不断压缩左边窗口，可以遍历出所有满足要求的窗口
                num-=nums[left];
                left++;
            }
        }
        return count;
    }
}