一套滑动窗口代码模板，直接搞定80道LeetCode算法题

前言：

滑动窗口是双指针的一种特例，可以称为左右指针，在任意时刻，只有一个指针运动，而另一个保持静止。滑动窗口路一般用于解决特定的序列中符合条件的连续的子序列的问题。

滑动窗口的时间复杂度是线性的，一般为O(n),滑动窗口的左右边界都不会向左滑动，向左滑动等于走回头路，是一种回溯的算法，很可能会陷入死循环。 滑动窗口是一种全遍历问题，一定会遍历到末尾的。

其本质思路在于：

1. 初始化将滑动窗口压满，取得第一个滑动窗口的目标值
2. 继续滑动窗口，每往前滑动一次，需要删除一个和添加一个元素，求最优的目标值

一、算法应用场景

关键词：

1. 满足XXX条件（计算结果、出现次数、同时包含）
2. 最长/最短
3. 子串/子数组/子序列

例如：长度最小的子数组

二、滑动窗口思路模板

2.1、滑动窗口使用思路（寻找最长）

————核心：左右双指针(L,R)在起始点，R向右逐位滑动循环

————每次滑动过程中

如果：窗内元素满足条件，R向右扩大窗口，并更新最优结果

如果：窗内元素不满足条件，L向右缩小窗口

————R到达结尾

2.2、滑动窗口使用思路（寻找最短）

————核心：左右双指针(L,R)在起始点，R向右逐位滑动循环

————每次滑动过程中

如果：窗内元素满足条件，L向右缩小窗口，并更新最优结果

如果：窗内元素不满足条件，R向右扩大窗口

————R到达结尾

三、滑动窗口代码模板

3.1、最长模板

初始化 left，right，result，bestResult
while("右指针没有到结尾"){
    窗口扩大，加入right对应元素，更新当前result
    while("result不满足要求"){
        窗口缩小，移除left对应元素，left右移
    }
    更新最优结果bestResult
    right++;
}
返回bestResult
复制代码

3.2、最短模板

初始化 left，right，result，bestResult
while("右指针没有到结尾"){
    窗口扩大，加入right对应元素，更新当前result
    while("result满足要求"){
        更新最优结果bestResult
        窗口缩小，移除left对应元素，left右移
    }
    right++;
}
返回bestResult
复制代码

四、小试牛刀(算法练手)

题目： [209. 长度最小的子数组]

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

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

示例 1 ：

输入： target = 7, nums = [2,3,1,2,4,3]
输出： 2
解释： 子数组 [4,3] 是该条件下的长度最小的子数组。
复制代码

示例 2 ：

输入： target = 4, nums = [1,4,4]
输出： 1
复制代码

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

算法实现：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 初始化 left，right，result，bestResult
        // result是当前的currSum、bestResult为mixLength
        int left = 0, right = 0,currSum = 0, mixLength = 0;
        // 右指针没有到结尾
        while(right < nums.length){
            // 窗口扩大，加入right对应元素，更新当前
            currSum += nums[right];
            // result满足要求
            while(currSum >= target){
                // 更新最优结果mixLength
                if(right - left + 1 < mixLength || mixLength == 0){
                    mixLength = right - left + 1;
                }
                // 窗口缩小，移除left对应元素，left右移
                currSum = currSum - nums[left];
                left++;
            }
            // right++
            right++;
        }
        // 返回mixLength
        return mixLength;
    }
}
复制代码

五：总结：

5.1：LeetCode原题209练习通道

更多算法练习以及算法模板请点击我的GitHub，创作不易，觉得有用可以在GitHub帮忙点个Starred，在这里表示感谢！也非常欢迎各位参与到我的github中LeetCode学习项目的贡献中（请私聊我），可以一起敲算法，在学习的道路上前进。