滑动窗口

滑动窗口 :laughing: O(n)

滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

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

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。

1. 窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

2. 窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

3. 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

时间复杂度问题

每个元素在滑动窗口往右扩大时进来一次，窗口缩小时出去一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)

leetcode 209 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路

1. 我们在数组nums 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引区间 [left, right] 称为一个「窗口」。
2. left不动，不断地增加 right 指针扩大窗口，直到窗口符合要求（窗口内数值之和>=target）。
3. 此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 ，直到窗口不再符合要求。
4. 重复第 2 和第 3 步，直到 right 到达数组末尾。

• 第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」

code

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int fast = 0;
        int slow = 0;
        int shortest = INT32_MAX;
        int sum = 0;
        int count = 0;
        while (fast < nums.size())
        {
            sum+=nums[fast];

            while (sum >= target)//while不断比较子序列是否符合条件
            {
                count = fast - slow + 1;
                shortest = count > shortest ? shortest : count;
                sum -= nums[slow++];//这里体现出滑动窗口的精髓之处，不断变更子序列的起始位置

            }
            fast++;
        }
        // 如果shortest没有被赋值的话，就返回0，说明没有符合条件的子序列
        return shortest == INT32_MAX ? 0 : shortest;
    }
};

leetcode 904 摘水果

上来就是一波判断猛如虎。结果运行的时候各种问题，然后开始各种修修补补，最后发现改了这里那里有问题，改了那里这里又跑不起来了。(真实写照hahahah)