核心思想

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。
有些书上把滑动窗口叫做虫爬法,两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动

废话不多说，开始刷题

643. 子数组最大平均数 I

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
示例：

输入：[1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for (int i = k; i < n; i++) {
            sum = sum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, sum);
        }
        //细节，一定要加 1.0 ，不然不会取小数
        return 1.0 * maxSum / k;
    }
}

424. 替换后的最长重复字符

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

注意：字符串长度 和 k 不会超过 104。
示例 1：

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

示例 2：

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

class Solution {
    public int characterReplacement(String s, int k) {
        //保存对应字母出现的次数
        int dp[] = new int[26];
        int maxCharater = 0;
        int left = 0;
        int right = 0;
        // 这里需要转换一下思维，题目可以转换为 ：
        //在一个滑动窗口内，数量最多的字母 + k 大于窗口的大小（right - left + 1）
        while (right < s.length()){
            dp[s.charAt(right) - 'A']++;
            maxCharater = Math.max(maxCharater, dp[s.charAt(right) -'A']);
            if (right - left + 1 - maxCharater > k){
                dp[s.charAt(left) - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }
}

1208. 尽可能使字符串相等

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

示例 1：

输入：s = "abcd", t = "bcdf", cost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

示例 2：

输入：s = "abcd", t = "cdef", cost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

示例 3：

输入：s = "abcd", t = "acde", cost = 0
输出：1
解释：你无法作出任何改动，所以最大长度为 1。

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int maxSub = 0;
        int left = 0;
        int right = 0;

        int[] costs = new int[s.length()];
        //每一步需要的花费保存起来
        for (int i = 0 ; i < s.length() ; ++i){
            costs[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }   
        int curCost = 0;
        while (right < s.length()){
            curCost += costs[right];
            //当前花费超出最大预算，左指针移动，花费减掉左一
            if (curCost > maxCost){
                curCost -= costs[left];
                left++;
            }
            maxSub = Math.max(maxSub,right - left + 1);
            right++;
        }
       return  maxSub;
    }