【算法专题突破】滑动窗口 - 长度最小的子数组（9）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法专题突破】滑动窗口 - 长度最小的子数组（9）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

1. 题目解析

题目链接：209. 长度最小的子数组 - 力扣（Leetcode）

【算法专题突破】滑动窗口 - 长度最小的子数组（9）,算法专题训练,leetcode,算法,c++

要注意的是，题目给的是正整数，

而题目要求并不难理解，就是找最短的子数组。

2. 算法原理

如果使用暴力的话，就是一个O(N3)的算法，复杂度很高，

我们可以用滑动窗口来做，滑动窗口是一个形象的名字，其实本质上也是一种双指针算法，

两个双指针同向移动，不回退，我们就将其称之为滑动窗口，因为就像窗口一样滑动。

那么我们怎么使用滑动窗口来做这道题呢？

1. 用两个指针作为窗口的左右边界

2. 进窗口

3. 判断如何出窗口

哪这道题来说：

【算法专题突破】滑动窗口 - 长度最小的子数组（9）,算法专题训练,leetcode,算法,c++

两个指针 left 和 right 先初始化成0，

如果和小于目标值就让right++，

如果和大于等于目标值就记录结果，然后让 left++。

3. 代码编写

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), sum = 0, len = INT_MAX;
        int left = 0, right = 0;
        while(right < n) {
            sum += nums[right];
            while(sum >= target) {
                len = min(len, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }
        return len == INT_MAX ? 0 : len;
    }
};