优选算法的智慧之光：滑动窗口专题(二)

专栏：算法的魔法世界

个人主页：手握风云

一、例题讲解

1.1. 最大连续1的个数 III

1.2. 找到字符串中所有字母异位词

1.3. 串联所有单词的子串

1.4. 最小覆盖子串

一、例题讲解

1.1. 最大连续1的个数 III

题目要求是二进制数组，也就是数组中的元素只有0和1。最多翻转k个0，而不是恰好，也就是当数组中0的个数小于k，就不用真的去翻转k个0。

如果我们按照题目要求解题，代码会非常不好写，因为我们还要去翻转0。我们可以转化一下，我们从数组当中找出一个最长子数组，并且这个子数组中0的个数不超过k个，这样我们就不用再去进行翻转0的操作。

我们先来思考一下暴力枚举：我们先固定数组当中的第一个元素为起点，然后向后移动，当子数组中0的个数超过k就停止（如下图所示）。我们还需要一个额外的变量zero来统计0的个数。

接下来根据暴力枚举进行优化。先定义left和right指针指向数组的第一个元素，然后让right指针向后移动。直到left与right所构成的子数组中0的个数大于k。根据暴力枚举的思路，接下来就让left指针也向右一位，right指针也要回退再向右移动。在这段区间内，right还是依旧走到我们原来的位置。

通过上面的分析，我们发现right指针不需要回退，让left指针直接越过这段区域。这时我们就会发现同向双指针，也就是利用滑动窗口来解决。步骤还是“进窗口→判断→出窗口→更新结果”。进窗口，当right遇到1的时候，无视；遇到0，zero+1。判断，当zero>k时，left向右移动，完成出窗口的操作。

public class Solution {
    public int longestOnes(int[] nums, int k){
        int ret = 0;
        for (int left = 0,right = 0,zero = 0;right < nums.length; right++){
            if(nums[right] == 0) zero++;//进窗口
            while(zero > k){//判断
                if(nums[left++] == 0) zero--;//出窗口
                ret = Math.max(ret,right-left+1);
            }
        }
        return ret;
    }
}

1.2. 找到字符串中所有字母异位词

我们看下上面的示例1，p可以重新排列为abc、acb、bac、bca、cab、cba。s中的索引则为[0,2]、[6,8]，最终输出结果为[0,6]。

首先我们需要思考如何判断两个字符串为异位词，我们可以利用两个哈希表来统计字符串中字母出现的个数，如果个数相等，则两个字符串为异位词。我们先来思考暴力解法：先把字符串p丢进hash1中，然后从字符串s中找到长度与p相等的子串丢进hash2中，并统计子串中出现的字母个数。

其实我们从上图中，很容易想到如何对暴力解法进行优化：统计完第一个子串，让里面的字符开始进出哈希表。就像窗口一样从头到尾，并且滑动窗口的长度是固定的，与p的长度相等。

然后我们就可以利用滑动窗口的步骤来解题：进窗口，把字符丢进hash2中；判断，当窗口的长度大于p的长度时，就要进行出窗口的操作；最后检查两个哈希表中的字符数量是否一致，更新结果。

由于题目当中的字符串仅包含小写字母，所以我们可以定义一个大小为26的数组来与哈希表判断是否相等，还需要判断进出窗口，这样时间复杂度就为26+n→ $O(n)$ 。但如果我们遇到更难的题目就可能会超时，我们还需要对最后的更新做优化。

我们再额外定义一个变量来统计“有效字符”的个数，这个“有效字符”指的是p中的字符。进入后，如果hash2中的有效字符小于hash1中的字符，则count++；出去前，我们需要检查出去的字符是否等于hash1中的字符，则出去的是有效字符。进出窗口的同时维护count的大小。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();

        int[] hash1 = new int[26];//统计p中每一个字符出现的个数
        for(char ch : pp) hash1[ch - 'a']++;

        int[] hash2 = new int[26];//统计窗口中字符出现的个数
        for (int left = 0,right = 0,count = 0;right < s.length(); right++){
            char in = ss[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;//进窗口与维护count
            if(right - left + 1 > p.length()){//判断
                char out = ss[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;//出窗口与维护count
            }
            if(count == p.length()) ret.add(left);
        }
        return ret;
    }
}

1.3. 串联所有单词的子串

题目要求我们，将字符串数组的子字符串串联，然后在字符串s中的一个字串找出字母异位词。与上一题类似，但这道题面对的是一个一个的字符串，但我们依然可以利用滑动窗口和哈希表来解决。首先在哈希表上，这里需要用到容器来映射字符串和字符串出现的次数；在指针移动上，right指针不能一次移动一个字符，长度应与words里的字符串长度一致。对于滑动窗口的执行次数（如下图），我们只需要执行这3次滑动窗口的操作就可以找出，其他操作都是多余的。所以滑动窗口的执行次数也是字符串数组中字符的长度。

完整代码实现：

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        Map<String,Integer> hash1 = new HashMap<String,Integer>();//保存words里面单词的频次
        for(String str : words) hash1.put(str, hash1.getOrDefault(str,0)+1);//把单词丢进哈希表里面，并单词个数
        int len = words[0].length(),m = words.length;
        for (int i = 0; i < len; i++) {//执行次数
            Map<String,Integer> hash2 = new HashMap<String,Integer>();//统计窗口内单词的频次
            for (int left = i,right = i,count = 0;right + len <= s.length();right += len){//count用来统计有效字符串的个数
                //进窗口与维护count
                String in = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;
                //判断
                if(right - left + 1 > len * m){
                    //出窗口与维护count
                    String out = s.substring(left,left+len);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out) - 1);
                    left += len;
                }
                if(count == m) ret.add(left);
            }
        }
        return ret;
    }
}

1.4. 最小覆盖子串

我们先理清题目要求：题目要我们从字符串s中找到一个最小子串，与字符串t构成包含关系。如何没有这样的子串，返回空字符串“”。

我们还是先来思考一下暴力解法：先定义两个指针，我们以其中一个指针为起点，另一个指针向右移动，找到所有符合条件的子串，从里面挑出最短的长度。如果转化成代码，依然是借助哈希表，将遍历过的字符丢进哈希表中进行统计直到里面的字符个数大于等于t中的即可。

接下来对暴力解法进行一个优化。我们看下图，我们从s中找出一段符合要求的子串，然后让left向后移动一步，此时会出现两种情况，要么缩小的区间还是符合要求，要么不符合要求，我们就让right向右移动，并且在这期间right是不需要回退的。这时候我们就可以用滑动窗口与双指针来解决。

进窗口，把s中的字符串丢进哈希表中统计。当窗口是合法的时候，判断两个哈希表里的字符个数，再让left向左移动。我们最后是要返回一个字符串，所以们需要知道起始位置和最终位置来决定我们什么时候出窗口。

如果我们只去遍历一遍哈希表，那么这个算法的时间复杂度是非常高的。我们还需要对算法进行优化。与前两题一样，在定义变量count。只不过这次的count是统计字符的种类，因为在找字母异位词时，子串和字符串是一一对应的关系，这里字符却是大于等于的关系。进窗口之后，比较hash1(in) == hash2(in)（这里之所以不是大于等于，是因为不会统计进重复的子串）。出之前，比较hash1(out) == hash2(out)，就能保证出之后窗口不是有效的。因为统计的是字符的种类，所以count = hash1的长度。

{
    public String minWindow(String s,String t){
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();

        int[] hash1 = new int[128];//统计字符串t中的频次
        int kinds = 0;//t中有多少种字符
        for(char ch : tt)
            if(hash1[ch]++ == 0) kinds++;
        int[] hash2 = new int[128];
        int minlen = Integer.MAX_VALUE, begin = -1;
        for(int left = 0,right = 0,count = 0;right < ss.length; right++){
            char in = ss[right];
            if(++hash2[in] == hash1[in]) count++;//进窗口与维护count
            while(kinds == count){//判断
                //更新结果
                if(right - left +1 < minlen){
                    begin = left;
                    minlen = right - left + 1;
                }
                char out = ss[left++];
                if(hash2[out]-- == hash1[out]) count--;//出窗口与维护count
            }
        }
        if(begin == -1) return new String();
        else return s.substring(begin,begin+minlen);
    }
}