滑动窗口算法模板

大致模板：

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
   Map<Character,Integer> maps= new HashMap<Character,Integer>();
        Map<Character,Integer> mapp= new HashMap<Character,Integer>();
    int tn=t.length();
        for(int i=0;i<tn;i++){  //把小的字符串添加进String中
            char a=p.charAt(i);
            mapp.put(a,mapp.getOrDefault(a,0)+1);
        }
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.length()) {
        // c 是将移入窗口的字符
         char a=s.charAt(right)
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
             char a=s.charAt(left)
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

PS：不管题目涉及一个字符串还是两个字符串都是while里面包含while，第一个while是扩大窗口第二个是满足条件下缩小窗口，再根据题目要求补充逻辑就好了

2024. 考试的最大困扰度（没写出来）

题目描述：

思路：

代码：

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(maxConsecutiveChar(answerKey, k, 'T'), maxConsecutiveChar(answerKey, k, 'F'));
    }
    public int maxConsecutiveChar(String answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey.charAt(right) != ch ? 1 : 0;
            while (sum > k) {
                sum -= answerKey.charAt(left++) != ch ? 1 : 0;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

1004. 最大连续1的个数 III（ac）

和上题的思路一样

代码：

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n=nums.length;
        int sum=0;
        int max=0;
        for(int left=0, right=0;right<n;right++){
            sum+=nums[right]==1?0:1;
            if(sum>k){
                sum-=nums[left++]==0?1:0;
            }
            max=Math.max(max,right-left+1);
        }
        return max;
    }
}

424. 替换后的最长重复字符（比前面两题更难想）

题目描述：

思路：滑动窗口，每次窗口维持一定的相同字符（包括替换在内），满足条件扩，不满足缩

代码：

//这题一看就是滑动窗口 每次窗口中保留
class Solution {  
    public int characterReplacement(String s, int k) {
         int n=s.length();
         //通过一个26的数组来存储每一个字符出现的次数
         int a[]=new int [26];
         //左指针 右指针
         int left=0,right=0;
         //记录最大数
         int max=0;
         int s1=0;
         //一次遍历  
         while(right<n){
             char temp=s.charAt(right);
             a[temp-'A']++;
             // 记录里面相同字符的最大个数
           max= Math.max(max,a[temp-'A']);

             while(right-left+1-max>k){
               char temp1 = s.charAt(left++);
               a[temp1-'A']--;
             }
        s1=Math.max(s1,right-left+1);
        right++;
         }
         return s1;
    }}