滑动窗口算法思路

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

需要考虑的问题

1.窗口内的元素是什么

2.左边边界判断

3.右边边界判断

一般形式：

int left = 0, right = 0;
while (right < s.size()) {
	windows.add(s[right]);
    right++;
    while (满足窗口滑动的条件) {
    	window.remove(s[left]);
        left++;
    }
}

注意：窗口左右边界具体先求谁，根据具体的情况而定，有些既可以先求左边界，也可以先求右边界。

例子说明

先求右边界

例1:长度最小的数组

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

解题思路

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

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

• 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。

1. 初始化windows左右边界left、right为0，既nums数组的起始位置

2. right遍历数组，并且求子数组和

3. 当子数组和大于等于目标值target，求出子数组长度，并找最小值，左边界开始收缩。

class Solution {
public:
    //双指针法：滑动窗口
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0,right = 0,sum = 0; //窗口起始位置，终止位置，序列和
        int result = INT_MAX; // 记录结果
        int windowsLength = 0; //窗口长度

        while(right < nums.size()) {
            sum += nums[right];
            right++;
            while(sum >= target) {
                windowsLength = (right - left);
                sum -=nums[left];
                left++;
                result = min(result, windowsLength);
            }
        }
        return result == INT_MAX? 0:result;
    }
};

先求左边界

例2：904. 水果成篮

题目链接

解题思路

• 收集的水果的最大数目，既子数组的最大长度
• 左边界判断 第一种水果的最左边值
• 右边界判断 第二种水果的最右边值

这时候如果采用右边界先确定的话，会造成 无法判断水果类型的后果

先确定左边界left 并且记录left所在的第一种水果

一次循环寻找在确定第一种水果后可以采摘的第二种水果

right作为右边界从left开始向右扩展 寻找可行解

在满足只采摘已知的两种水果的前提下 不断扩展右边界寻找最优解

无最优解后移动左边界寻找新的可行解

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        //滑动窗口
        int left = 0, right = 0;
        int first = 0, second = 0;
        int windowsLength = 0,result = INT_MIN;

        for (;left < fruits.size(); left++) {
            first = fruits[left];
            for (int i = left; i < fruits.size(); i++) {
                if (fruits[i] != first) {
                    second = fruits[i];
                    break;
                }
            }
            while (fruits[right] == first || fruits[right] == second) {
                windowsLength = right - left + 1 ;
                result = result > windowsLength ? result : windowsLength;
                right++;

                if (right == fruits.size()) {
                    return result == INT_MIN ? 0 : result;
                }
            } 
        }
        return result;
    }
};

感谢 代码随想录 斜行