【算法】滑动窗口——长度最小的子数组

本篇文章是用一个实例来介绍常用算法之一“滑动窗口”的相关概念，有需要借鉴即可。

1.题目

想要介绍一个算法，没有具体的例子来说算法是非常抽象的，算法是一种思想，因而为了介绍有关滑动窗口的概念，用下面例子来做相关介绍。

题目链接：LINK

看到这个题目我们先不论什么是“滑动窗口”这种算法，我们先从最简单的暴力求解来思考，顺着暴力求解的思路一步一步优化，最终达到“滑动窗口”的算法效果。

2.暴力求解

2.1暴力求解思路：

两个指针，一个left，一个right，加上left和right之间的所有数跟target进行比较，找到最小的len即可。

我们以上面的题目为例子，以题目中示例1为具体的操作对象：

left和right的组合共有36种情况，如下图所示：

2.2时间复杂度是多少？

答：left和right两层循环并且求sum时候需要再遍历一次，所以是N^3

当然这种代码很挫哈，为了提高效率，我们引出“滑动窗口”这一算法思想。

3.暴力求解的优化

滑动窗口是一种高效的算法，说白了也是从暴力求解的思路中优化过来的，所以我们一步一步来优化该暴力求解思路，来更加高效。

3.1固定left的情况下，优化right的次数。

在同一个left的情况下，很多时候right是多余的。比如说2 + 3 + 1 + 2 = 8早就超过target = 7了，暴力求解还在继续向后加…这很多余。

3.2sum求值优化

求和的时候，每次left和right变的情况下都要重新计算，十分耗费性能。我们想是不是可以利用一下上一次的sum值来求这次的sum值？

经过优化，这样就基本接近滑动窗口算法了。但还不是。这时的时间复杂度是O(N^2)
在本题中大概优化到下面效果：

大概就是下面的代码：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int ret = INT_MAX;
        int n = nums.size();
        // 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
        // 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩
        // 枚举开始位置
        for (int start = 0; start < n; start++)
        {
        int sum = 0; // 记录从这个位置开始的连续数组的和
        // 寻找结束位置
        for (int end = start; end < n; end++)
        {
         sum += nums[end]; // 将当前位置加上
 
        if (sum >= target) // 当这段区间内的和满⾜条件时
           {
           // 更新结果，start 开头的最短区间已经找到
           ret = min(ret, end - start + 1);
           break;
           }
        }
        }
        // 返回最后结果
        return ret == INT_MAX ? 0 : ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

不用怀疑，力扣过不了哈。

3.3不同组之间left与right包含关系的优化

这个是什么意思呢？
嗯…经过上面所说的两步之后，我们就发现以上面的题目来举例，暴力求解就可以达到下面这种优化效果：

当然，上面超出时间限制截图告诉我们，继续优化…
但是我们发现一个问题，比如拿下面的例子来说(看蓝色框)

放大一点：

就是这种不满足的包含情况下也可以优化掉。
下面是真正的滑动窗口优化图：

4.滑动窗口算法

4.1概念

基于双指针算法，两指针同向向前且不回退的算法思想。

4.2应用场景

具有一定单调性题目，比如在本节博客的举的这道题种，从left到right不断加就是一种单增关系。

4.3使用

滑动窗口的大体使用步骤是什么呢？

• 1.left，right
• 2.进窗口
• 3.判断
  • 出窗口
  • 更新结果

注：①2、3两步是循环；②本步骤只是大体步骤；

比如说，在本例子中，这个步骤就可以具体为：

• 1.先让left = 0，right = 0；
• 2.进窗口，sum +=2；
• 3.判断sum < target；
• 4.所以继续进窗口，让right = 1，sum+=3；
• 5.继续判断，sum = 5 < target
• 6.继续进窗口，right = 2，sum+=1
• 7.继续判断，sum = 6 < target
• 8.继续进窗口，right = 3，sum+=2
• 9.继续判断，sum = 8 > target
• 10.满足条件，出窗口
• 11.left++，left = 1，sum-=2
• 12.判断sum = 6 < target
• 13.right++，right = 4，sum+=4
• 14.判断sum = 10 > target
• 。。。

4.4正确性

滑动窗口算法对吗？是正确的。
因为只是在暴力求解的基础上去掉了一些不必要的计算过程。

4.5时间复杂度

对于上面那道题来说，暴力求解是O(N^3)，但是滑动窗口是O(N)

5.题解代码示例

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int ret = INT_MAX;
        int n = nums.size();
        int sum = 0;
       for(int left = 0,right = 0;right < n;right++)
        {
            sum+=nums[right];//进窗口
            while(sum>=target)//判断
            {
                ret = min(ret,right - left + 1);
                sum-=nums[left];//出窗口
                left++;//持续判断
            }
        }
        // 返回最后结果
        return ret == INT_MAX ? 0 : ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

EOF