滑动窗口例题

1.适合解决的题目类型

滑动窗口，可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“请找到满足xx的最x的区间（子串、子数组）的xx”这类问题都可以使用该方法进行解决。

2.例题

面试题 17.18. 最短超串

 主要思想就是先用右指针去寻找覆盖了子串的母串部分，然后滑动左侧边界，直到不满足覆盖条件。

代码及注释如下

class Solution {
    public int[] shortestSeq(int[] big, int[] small) {
        //左右双指针表示滑动窗口，start和min用来保存最优解
        int left = 0,right = 0,start = 0;
        int min = Integer.MAX_VALUE;
        //window用来记录当前窗口包含的字符和出现的次数
        //needs用来记录small当中出现的字符和包含的次数
        HashMap<Integer,Integer> window = new HashMap<>();
        HashMap<Integer,Integer> needs = new HashMap<>();
        //记录small中出现的字符和包含的次数
        for(Integer c:small ) needs.put(c,needs.getOrDefault(c,0)+1);
        //match用来保存匹配的个数
        int match = 0;
        //移动right扩大窗口
        while(right<big.length){
            Integer c1 = big[right];
            if(needs.containsKey(c1)){
                window.put(c1,window.getOrDefault(c1,0)+1);
                if(window.get(c1)==needs.get(c1)){
                    match++;
                }
            }
            right++;
            //当匹配个数满足small时，移动 left 缩小窗口进行优化
            while (match==needs.size()){
                //更新最小窗口
                if(right-left<min){
                    start = left;
                    min = right-left;
                }
                Integer c2 = big[left];
                if(needs.containsKey(c2)){
                    window.put(c2,window.getOrDefault(c2,0)-1);
                    if(window.get(c2)<needs.get(c2)){
                        match--;
                    }
                }
                left++;
            }
        }
        return min == Integer.MAX_VALUE? new int[0]:new int[]{start,min+start-1};
    }
}