滑动窗口 | kk的小窝

滑动窗口，顾名思义，就是“滑动”的窗口。我们在处理数组的子区间问题（如求出数组 array 的某个子区间的长度）时，可以同时使用两个指针（也可以说是下标）： start 和 end ，在这个数组中“圈出”一个窗口，并根据条件移动右边界 end 或左边界 start ，实现窗口的“滑动”。

这种算法能够将时间复杂度从O(n^2)优化为O(n)，

滑动窗口有三种形式：固定长度窗口，最大窗口和最小窗口。

固定窗口

这是最简单的情况，此时滑动窗口的长度 length 固定为 end - start + 1 ，每次移动都将 end 和 start 加一，直到右边界碰到数组的边界 array.length：

LeetCode T643：子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10^(-5) 的答案都将被视为正确答案。

class Solution {
    public double findMaxAverage(int[] nums, int k) {

        // 维护初始窗口
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        // 移动窗口
        double avg = sum / k;
        for (int end = k; end < nums.length; end++) {

            // 计算窗口的起始下标 start
            int start = end - k;

            // 计算窗口移动之后的数字和
            sum += nums[end];
            sum -= nums[start];

            // 计算平均值，取最大
            avg = Math.max(avg, sum / k);    
        }

        return avg;
    }
}

最大窗口

在这种情况下，窗口长度要在满足要求的情况下尽可能大，但是移动的逻辑和边界条件仍然为“每次移动都将 end 和 start 加一，直到右边界碰到数组的边界 array.length”

LeetCode T3090：每个字符最多出现两次的最长子字符串

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

子字符串是字符串中连续的字符序列

class Solution {
    public int maximumLengthSubstring(String s) {

        // 哈希表，记录字符串的出现次数
        Map<Character, Integer> charCount = new HashMap<>();

        // 滑动窗口首下标
        int start = 0;

        // 子字符串最大长度
        int maxLength = -1;

        // 尾下标遍历
        for (int end = 0; end < s.length(); end++) {

            // 当前字符
            char c1 = s.charAt(end);

            // 将字符添加进哈希表
            if (!charCount.containsKey(c1)) {
                charCount.put(c1, 1);
            } else {
                charCount.put(c1, charCount.get(c1) + 1);
            }

            // 根据条件收缩首下标
            while (charCount.get(c1) > 2) {
                char c2 = s.charAt(start++);
                charCount.put(c2, charCount.get(c2) - 1);
            }

            // 计算子字符串长度，取最大值
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }
}

最小窗口

在这种情况下，窗口长度则需要在满足要求的情况下尽可能小，但是移动的逻辑和边界条件仍然为“每次移动都将 end 和 start 加一，直到右边界碰到数组的边界 array.length”

LeetCode T209：长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {

        int sum = 0;
        
        // 如果整个序列的元素和小于 target，那么自然不存在子序列满足要求
        for (int num : nums) {
            sum += num;
        }
        if (sum < target) {
            return 0;
        }

        sum = 0;
        int start = 0;
        int minLength = nums.length;
        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];

            // 一直收缩，直到不满足要求
            while (sum >= target) {
                minLength = Math.min(minLength, end - start + 1);
                sum -= nums[start++];
            }
        }

        return minLength;
    }
}