滑动窗口 解题思路

算法应用场景

关键词：

满足 xxx 条件 （计算结果，出现次数，同时包含）
最长 / 最短
子串 / 子数组 / 子序列

例如：长度最短的子串

滑动窗口解题思路

1. 寻找最长

左右双指针（L R） 在起始点，R向右逐位滑动循环，每次滑动过程中，

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

直到 R 滑动到尾部结束

// 寻找最长模板
// 初始化 left、right、result、bestResult

while( 右指针没有到结尾 ) {
	窗口扩大，加入 right 对应元素，更新当前 result
	while( result 不满足要求 ) {
		窗口缩小，移除 left 对应元素， left 右移
	}
	更新最优结果 bestResult
	right++
}
return bestResult
1
2
3
4
5
6
7
8
9
10
11
12

2. 寻找最短

左右双指针（L R） 在起始点，R向右逐位滑动循环，每次滑动过程中，

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

直到 R 滑动到尾部结束

// 寻找最短模板
// 初始化 left、right、result、bestResult

while( 右指针没有到结尾 ) {
	窗口扩大，加入 right 对应元素，更新当前 result
	while( result 满足要求 ) {
		更新最优结果 bestResult
		窗口缩小，移除 left 对应元素， left 右移
	}
	right++
}
return bestResult
1
2
3
4
5
6
7
8
9
10
11
12

以 LeetCode 209. 长度最小的子数组 为例：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sum = 0, bestResult = 0;
        while(right < nums.size()) {
            sum += nums[right];
            while(sum >= target) {  
                if(bestResult > (right - left + 1) || bestResult == 0)  {// 让第一次能进来
                    bestResult = right - left + 1;
                }            
                sum -= nums[ left++ ];
            }
            right++;           
        }
        return bestResult;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17