首页 算法

# 介绍

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

从类型上说主要有：

  • 固定窗口大小
  • 窗口大小不固定，求解最大的满足条件的窗口
  • 窗口大小不固定，求解最小的满足条件的窗口

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

# 固定窗口大小

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

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

# 可变窗口大小

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

  1. l 和 r 都初始化为 0 (左边界也可以初始化为 - 1，后面就节省操作，不过都可以，仁者见仁智者见智吧)
  2. r 指针移动一步
  3. 判断窗口内的连续元素是否满足题目限定的条件
    • 3.1 如果满足，再判断是否需要更新最优解，如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行 3.1
    • 3.2 如果不满足，则继续。
      形象地来看的话，就是 r 指针不停向右移动，l 指针仅仅在窗口满足条件之后才会移动，起到窗口收缩的效果。

力扣第三题 (剑指 offer48 题) 用滑动窗口解决代码

// 方法二：滑动窗口，就是滑动窗口的最简单的模型，很简单啊 我为啥花费那么时间进行思考呢，0.0.0.0
    public int lengthOfLongestSubstring2(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, left = -1;// 滑动窗口的边界，边界其实要为 - 1，不然后面会出大问题
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {// 有重复数字，开始滑动窗口
                // 初始化为 0 的话，需要进行右边的加一操作， left = Math.max (left,map.get (s.charAt (i)) + 1);
                left = Math.max(left, map.get(s.charAt(i)));
            }
            // 没有重复数字（没有走上面的 if 判断）
            map.put(s.charAt(i), i);
            // 初始化为 0 的话，需要进行右边的加一操作，max = Math.max (max,i-left+1);
            max = Math.max(max, i - left); 
        }
        return max;
    }