基础算法—滑动窗口篇

滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

实现滑动窗口，主要确定如下三点：

窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？

滑动窗口 + 变量计数模板：

class Solution {
    public int slidingWindow(int[] nums, int k) {
        //数组/字符串长度
        int n = nums.length;
        //双指针，表示当前遍历的区间[left, right]，闭区间
        int left = 0, right = 0;
        //定义变量统计 子数组/子区间 是否有效
        int sum = 0;
        //定义变量动态保存最大 求和/计数
        int res = 0;

        //右指针遍历到数组尾
        while (right < n) {
            //增加当前右指针对应的数值
            sum += nums[right];
            //当在该区间内 sum 超出定义范围
            while (sum > k) {
                //先将左指针指向的数值减去
                sum -= nums[left];
                //左指针右移
                left++;
            }
            //到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
            res = Math.max(res, right - left + 1);
            //移动右指针，去探索下一个区间
            right++;
        }
        return res;
    }
}

209. 长度最小的子数组

713. 乘积小于 K 的子数组

思路

//每次右指针位移到一个新位置，应该加上 x 种数组组合：
         //  nums[right]
         //  nums[right-1], nums[right]
         //  nums[right-2], nums[right-1], nums[right]
         //  nums[left], ......, nums[right-2], nums[right-1], nums[right]
         //共有 right - left + 1 种

乘积小于 K 的子数组

1004. 最大连续1的个数 III

思路

将题目目的转为：求连续子数组，要求长度最大，0 最多为k

用滑动窗口，让右指针一直右移，记录0 的个数，记录长度，当0 大于k，则左指针右移

15. 三数之和

思路

三数之和

18. 四数之和

思路

四数之和

滑动窗口 + 哈希表存储模板：

class Solution {
    public String slidingWindow(String s, String t) {
        //创建两个哈希表，分别记录 [需要的] 和 [加入的]
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> map = new HashMap<>();

        //创建 [双指针] 和 [有效数量]
        int left = 0, right = 0;
        int valid = 0;

        //外层循环，供右指针遍历
        while(right < s.length()){
            //创建临时 c 字符，是移入 窗口 内的字符
            char c = s.charAt(right);
            
            //进行窗口一系列逻辑更新
            ...
            
            //判断左指针是否要右移即窗口收缩：有效数量足够满足条件
             /*  可能是规定的窗口大小超出了，可能是有效值数量达成了
             1.  while(valid == need.size())
             2.  while(right - left + 1 >= s1.length())      
             */           
            while(windows need shrink){
                // 创建 d 是要移除窗口的字符
                char d = s.charAt(left);
                left++;

                //进行窗口一系列逻辑更新
                ...
            }
            
            //右指针右移
            right++;
        }
    }
}