滑动窗口框架
从整体到细节，自顶向下，从抽象到具体的框架思维是通用的，不只是学习数据结构和算法，学习其他任何知识都是高效的。
# 双指针技巧
不论是链表还是数组，双指针的技巧都可以使用。
双指针的技巧可以分为两类，一类是快慢指针，一类是左右指针。前者主要解决链表中的问题，比如链表中是否有环的判定并给出环的起点位置，寻找链表中点，寻找链表倒数第 k 个元素等。后者主要解决数组（或字符串）问题，比如二分查找，有序数组的两数之和，反转数组以及非常经典的滑动窗口算法。
# 滑动窗口算法
滑动窗口算法可以说是双指针的最高境界了，该算法的大致框架如下。
void SlidingWindow(string s, string t)
{
unordered_map<char, int> need, window;
for(char c: t) need[c] ++; // 添加元素给目标集合
int left = 0, right = 0; // 左闭右开区间
int valid = 0; // 记录有效元素的个数
while(right < s.size())
{
// c 为即将加入窗口的字符
char c = s[right];
++ right;
// 1. 窗口内的数据更新
// ...
// 2. 窗口何时收缩
while(window needs shrink)
{
// 3. 判断是否满足 need 条件
// ...
// d 是即将移出窗口的字符
char d = s[left];
++ left;
// 4. 窗口内的数据更新
// ...
}
}
}
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
30
31
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
30
31
只要回答好代码框架中的四个问题，那么这道滑动窗口的问题基本就 💯
以后只要遇到子串问题，基本都可以使用这个框架完美解决！注意子串与子序列的不同，比如 ace 是 abcde 的子序列，但不是子串，abc 是 abcde 的子串，同时也是其子序列。