什么是滑动窗口

滑动窗口可以看成数组中框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优的结果。

对于这道题来说，数组就是正整数序列 [1, 2, 3, ····, n]。我们设滑动窗口的左边界为 i，右边界为 j，则滑动窗口框起来的是一个左闭右开区间 [i,j)。注意，为了编程的方便，滑动窗口一般表示成一个左闭右开区间。在一开始，i=1, j=1，滑动窗口位于序列的最左侧，窗口大小为零。

image.png
滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)。如果左右边界向左移动的话，这叫做“回溯”，算法的时间复杂度就可能不止O(n)。

滑动窗口框架

public String slidingWindow(String s, String t) {
    MyMap<Character> window = new MyMap<>(), need = new MyMap<>();

    //初始化t，加快访问速度
    for (char c : t.toCharArray()) need.add(c);

    int left = 0, right = 0;
    int valid = 0;
    int start = 0, ans = Integer.MAX_VALUE;
    while (right < s.length()) {
        char c = s.charAt(right); //c是将移入窗口的字符
        right++; //窗口右移

        //todo ... 进行窗口内右移后的一系列更新的代码

        System.out.printf("win:[%d,%d)", left, right); //debug

        //判断左侧窗口是否要收缩
        while (window need shrink) {
            char d = s.charAt(left); //d是移除窗口的字符
            left++; //左移窗口

            //todo ... 进行窗口内左移后的一系列更新的代码
        }
    }
}

public class MyMap<K> extends HashMap<K, Integer> {
    public void add(K key) {
        this.put(key, this.getOrDefault(key, 0) + 1);
    }

    public void sub(K key) {
        this.put(key, this.getOrDefault(key, 0) - 1);
    }
}

题目一:和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

要用滑动窗口解这道题，我们要回答两个问题：

  • 第一个问题，窗口何时扩大，何时缩小？
  • 第二个问题，滑动窗口能找到全部的解吗？

对于第一个问题，回答非常简单：

  • 当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
  • 当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
  • 当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)，那么我们已经找到了一个 i 开头的序列，也是唯一一个 i 开头的序列，接下来需要找 i+1 开头的序列，所以窗口的左边界要向右移动
vector<vector<int>> findContinuousSequence(int target) {
    int l = 1, r = 1;
    int sum = 0;
    vector<vector<int>> ans;
    while (l <= target / 2) {
        if (sum < target) {
            sum += r++;
        } else if (sum > target) {
            sum -= l++;
        }
        if (sum == target) {
            vector<int> t;
            for (int i = l; i < r; i++) {
                t.push_back(i);
            }
            ans.push_back(t);
            sum -= l++;
        }
    }
    return ans;
}

题目二：优美子数组

给你一个整数数组 nums 和一个整数 k。如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目。

  1. 因为「优美子数组」只跟奇数和偶数有关，可以将偶数视为 0，奇数视为 1 ，以简化分析，所以用例在我们眼里应该变成这个样子
    d8c343b75085afaf35d342773f3eb2b5c8b0a1e42e8056ba2790a99100fc27ad图片.png
  2. 看一下这个用例，有多少个「优美子数组」。
    • 通过火眼金睛的观察，找到了数组中的两个奇数
    • 当满足 k=2 条件时，会有这 6 个「优美子数组」

dwfewx.png

  1. 使用滑动窗口
    • 根据「优美子数组」的特点，我们先设定满足 K 个奇数作为窗口
    • 找到窗口之后，需要知道窗口前面的个数和后面的个数
    • 如果使用一个数组来记录奇数的索引，对这个数组相邻元素做减法即可知道原数组两个奇数之间有几个元素，即图中窗口的左边索引保存在 odd[1] 中，那前面的个数就等于 odd[1] - odd[0]

为了方便计算，原数组前后都插入了假奇数
2sdfrvfdbb.png

  1. 为了在一次循环里搞定所有事情，还有个小问题需要解决
    • 当前遍历到窗口右边的索引，那它后面的个数暂时还无法得到（即图中的 odd[3]）
    • 为了解决这个问题，只好将窗口升级，让它覆盖 k + 1 个奇数
      虽然窗口变大了，但是我们只是为了得到计算每个窗口所需的 4 个奇数索引，所以题意不会有问题
int numberOfSubarrays(vector<int> &nums, int k) {
    vector<int> odd;//odd数组用来记录奇数的索引
    odd.push_back(-1);
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] % 2 == 1) {
            odd.push_back(i);
        }
    }
    odd.push_back(nums.size());
    int n = odd.size();
    if (n - 2 < k) {
        return 0;
    }
    int l = 1, r = 1, sum = 0, ans = 0;
    //在odd数组的[1,odd.size()-1]中滑动窗口，寻找奇数总数为k+1的窗口
    while (l <= r && r <= n - 1) {
        if (sum < k + 1) {
            sum++;
            r++;
        } else if (sum > k + 1) {
            sum--;
            l++;
        }
        if (sum == k + 1) {
            int left = odd[l] - odd[l - 1];
            int right = odd[r - 1] - odd[r - 2];
            ans += left * right;
            sum--;
            l++;
        }
    }
    return ans;
}

题目三：最小覆盖子串

public String minWindow(String s, String t) {
    MyMap<Character> window = new MyMap<>(), need = new MyMap<>();

    //初始化t，加快访问速度
    for (char c : t.toCharArray()) need.add(c);

    int left = 0, right = 0;
    int valid = 0;
    int start = 0, ans = Integer.MAX_VALUE;
    while (right < s.length()) {
        char c = s.charAt(right); //c是将移入窗口的字符
        right++; //窗口右移

        //进行窗口内的一系列更新
        if (need.containsKey(c)) {
            window.add(c);
            if (window.get(c).equals(need.get(c)))
                valid++;
        }

        //判断左侧窗口是否要收缩
        while (valid == need.size()) {
            //更新最小覆盖子串
            if (right - left < ans) {
                start = left;
                ans = right - left;
            }

            char d = s.charAt(left); //d是移除窗口的字符
            left++; //左移窗口

            //进行窗口内的一系列更新
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d)))
                    valid--;
                window.sub(d);
            }
        }
    }
    return ans == Integer.MAX_VALUE ?
            "" : s.substring(start, start + ans);
}

hhhhh