title: 滑动窗口
copyright: true
toc: true
tags:

• 滑动窗口
• 算法
• Java
  categories: 计算机
  declare: true
  mathjax: true
  abbrlink: 50cab45
  date: 2021-02-02 10:10:20

滑动窗口

双指针同类问题：

「力扣」第 3 题：无重复字符的最长子串；
「力扣」第 209 题：长度最小的子数组；
「力扣」第 76 题：最小覆盖子串；
「力扣」第 438 题：找到字符串中所有字母异位词；
「力扣」第 567 题：字符串的排列。

初识

1、题目：替换后的最长重复字符串

同类问题：

「力扣」第 1004 题：最大连续 1 的个数 III；
「力扣」第 1208 题：尽可能使字符串相等；
「力扣」第 1493 题：删掉一个元素以后全为 1 的最长子数组。

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

2、题解——什么是滑动窗口

解题思路：

• 本题是比较典型的滑动窗口问题
• 这类问题一般通过一个滑动窗口就能在 O(N) 的时间复杂度下求解

本题可以先退化成考虑 的情况，此时题目就变成了求解字符串中最长连续子串长度问题了。
我们先可以通过这个特例先了解一下滑动窗口的求解过程

上图的求解过程展示中，窗口从左至右不断扩张/滑动，当窗口触达字符串末尾字符时，运算结束，窗口的宽度为最终结果。初始窗口的宽度为 1，我们不断的通过向当前窗口覆盖的子串后面追加一个字符看是否能满足我们的要求，如果满足窗口扩张，如果不满足，窗口向右滑动。

当 时，子串的条件变成了允许我们变换子串中的 个字符使其变成一个连续子串

那么这个题的关键点就是我们如何判断一个字符串改变 个字符，能够变成一个连续串

如果当前字符串中的出现次数最多的字母个数 大于串长度，那么这个串就是满足条件的

我们维护一个数组 int[26] 来存储当前窗口中各个字母的出现次数，表示窗口的左边界， 表示窗口右边界

窗口扩张：不变，
窗口滑动：，
保存滑动窗口内相同字母出现次数的 历史 最大值，通过判断窗口宽度 #card=math&code=%28right%20-%20left%20%2B%201%29)是否大于 来决定窗口是否做滑动，否则窗口就扩张。

3、参考链接

作者：migoo
网址链接
来源：力扣（LeetCode）

4、代码

class Solution {
    public int characterReplacement(String s, int k) {
        int[] map = new int[26]; //记录窗口中的不同字符的数量
        int left = 0 , right = 0, hisMaxLength = 0;
        for (right = 0 ; right < s.length() ; right++){ //注意right在何处增加，以及因此right-left的值是否要加1
            int index = s.charAt(right) - 'A';
            map[index]++;
            hisMaxLength = Math.max(hisMaxLength,map[index]);
            if (right - left + 1 > hisMaxLength + k){
                map[s.charAt(left)-'A'] --; //当窗口移动时，其中记录的字符数量也应该发生改变
                left++;
            }
        }
        return s.length()-left;
    }
}

训练

1、题1004

class Solution {
    public int longestOnes(int[] A, int K) {
        int[] map = new int[2];
        //由于其只有0，1，故直接记录0的数量即可countZero
        int left = 0 , right = 0 , countZero = 0;
        while(right < A.length){
            int index = A[right];
            map[index]++;
            countZero = map[0];

            if( countZero > K){
                map[A[left]] -- ;
                left++;
            }
            right ++;
        }
        return A.length-left;
    }
}

2、题567-字符串的排列

一、题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。

二、题解

本题是类似一个==“最长连续子数组”==的问题，这里不过是将长度固定，所以可以使用滑动窗口（双指针）来解决该题：

由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。

根据这一性质，记 的长度为 ，我们可以遍历中的每个长度为 的子串，判断子串和 中每个字符的个数是否相等，若相等则说明该子串是 的一个排列。

使用两个数组 和， 统计 中各个字符的个数， 统计当前遍历的 子串中各个字符的个数。

由于需要遍历的子串长度均为 ，我们可以使用一个固定长度为 的滑动窗口来维护 ：滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符。然后，判断 是否与 相等，若相等则意味着 的排列之一是 的子串。

public boolean solution1(String s1, String s2){
        int n = s1.length();
        int m = s2.length();
        if (n > m ) return false;
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        for (int i = 0 ; i < n; i++){
            count1[s1.charAt(i)-'a']++;
            count2[s2.charAt(i)-'a']++;
        }
        if (Arrays.equals(count1,count2)){
            return true;
        }
        for (int i = n ; i < m ; i++){
            count2[s2.charAt(i)-'a']++;
            count2[s2.charAt(i-n)-'a']--;
            if (Arrays.equals(count1,count2)){
                return true;
            }
        }
        return  false;
    }

但是该方法中多次使用Arrays.equals()，可以采用以下思路进行简化：

注意到每次窗口滑动时，只统计了一进一出两个字符，却比较了整个 和数组。

从这个角度出发，我们可以用一个变量来记录 与 的不同值的个数，这样判断和 是否相等就转换成了判断 是否为。

每次窗口滑动，记一进一出两个字符为和。

若则对无影响，可以直接跳过。

若对于字符，在修改 之前若有 ，则将 加一；在修改 之后若有，则将 减一。字符同理。

此外，为简化上述逻辑，我们可以只用一个数组，其中，将 与 的比较替换成与 的比较。

public boolean solution2(String s1, String s2){
        //solution1中频繁使用Arrays.equals()来进行数组比较，浪费时间，可以使用diff记录两者的不同个数
        int n = s1.length();
        int m = s2.length();
        if (n > m ) return false;
        int diff = 0;
        int[] count = new int[26];
        for (int i = 0 ; i < n; i++){
            count[s1.charAt(i)-'a']--;
            count[s2.charAt(i)-'a']++;

        }
        for (int i : count){
            if(i!=0) diff++;
        }
        if (diff == 0) return true;

        for (int i = n ; i < m ; i++){
            int x = s2.charAt(i)-'a' , y = s2.charAt(i-n) - 'a';
            if(x==y) continue;
            if (count[x] == 0) diff++;
            count[x]++;
            if (count[x] == 0) diff--;
            if (count[y] == 0) diff++;
            count[y]--;
            if (count[y]==0) diff--;
            if (diff == 0 ) return true;
        }
        return false;
    }