The Sliding Problem contains a sliding window which is a sub – list that runs over a Large Array which is an underlying collection of elements.
滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。
比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。
如果题目中求的结果有以下情况时可使用滑动窗口算法：
/* 滑动窗口算法框架 */
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++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
滑动窗口算法的思路：
needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。
开始套模板之前，要思考以下四个问题：
LeetCode题目：76.最小覆盖子串
题目中包含关键字：时间复杂度O(n)、字符串、最小子串。可使用滑动窗口算法解决。
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
更新 window 中加入字符的个数，判断 need 与 window 中的字符个数是否相等，相等则 valid++ 。
2、什么条件下，窗口应该暂停扩大，开始移动_left_ 缩小窗口？
当 window 包含 need 中的字符及个数时，即 valid == len(need) 。
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
更新 window 中移出字符的个数，且判断 need 与 window 中的移出字符个数是否相等，相等则 valid-- 。
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
在缩小窗口时，因为求的是最小子串。
func minWindow(s string, t string) string {
need, window := make(map[byte]int), make(map[byte]int)
for i := 0; i < len(t); i++ { // 初始化 need
if _, ok := need[t[i]]; ok {
need[t[i]]++
} else {
need[t[i]] = 1
}
}
left, right, valid := 0, 0, 0
start, slen := 0, len(s)+1 // 设置长度为 len(s) + 1 表示此时没有符合条件的子串
for right < len(s) { // 滑动窗口向右扩大
c := s[right]
right++
if _, ok := need[c]; ok { // 向右扩大时，更新数据
if _, ok := window[c]; ok {
window[c]++
} else {
window[c] = 1
}
if window[c] == need[c] {
valid++
}
}
for valid == len(need) { // 当窗口包括 need 中所有字符及个数时，缩小窗口
if right-left < slen { // 缩小前，判断是否最小子串
start = left
slen = right - left
}
d := s[left]
left++
if v, ok := need[d]; ok { // 向左缩小时，更新数据
if window[d] == v {
valid--
}
window[d]--
}
}
}
if slen == len(s)+1 { // 长度 len(s) + 1 表示此时没有符合条件的子串
return ""
} else {
return s[start : start+slen]
}
}
LeetCode题目：567.字符串的排列
题目中包含关键字：字符串、子串，且求 s2 中是否包含 s1 的排列，即求是否包含长度 k 的子串。可使用滑动窗口算法解决。
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
更新 window 中加入字符的个数，判断 need 与 window 中的字符个数是否相等，相等则 valid++ 。
2、什么条件下，窗口应该暂停扩大，开始移动_left_ 缩小窗口？
当 window 包含 need 中的字符及个数时，即 valid == len(need) 。
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
更新 window 中移出字符的个数，且判断 need 与 window 中的移出字符个数是否相等，相等则 valid-- 。
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
无论在扩大时或缩小窗口时都可以，因为求的是固定长度的子串。选择在缩小窗口时更新。
func checkInclusion(s1 string, s2 string) bool {
if s1 == s2 {
return true
}
need, window := make(map[byte]int), make(map[byte]int)
for i := 0; i < len(s1); i++ {
if _, ok := need[s1[i]]; ok {
need[s1[i]]++
} else {
need[s1[i]] = 1
}
}
left, right := 0, 0
valid := 0
for right < len(s2) {
c := s2[right]
right++
if _, ok := need[c]; ok {
if _, ok := window[c]; ok {
window[c]++
} else {
window[c] = 1
}
if window[c] == need[c] {
valid++
}
}
for valid == len(need) {
if right-left == len(s1) {
return true
}
d := s2[left]
left++
if _, ok := need[d]; ok {
if _, ok := window[d]; ok {
if window[d] == need[d] {
valid--
}
window[d]--
}
}
}
}
return false
}
LeetCode题目：438.找到字符串中所有字母异位词
题目中包含关键字：字符串，且求 s 中的所有 p 的字母异位词的子串。可使用滑动窗口算法解决。
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
更新 window 中加入字符的个数，判断 need 与 window 中的字符个数是否相等，相等则 valid++ 。
2、什么条件下，窗口应该暂停扩大，开始移动_left_ 缩小窗口？
当 window 包含 need 中的字符及个数时，即 valid == len(need) 。
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
更新 window 中移出字符的个数，且判断 need 与 window 中的移出字符个数是否相等，相等则 valid-- 。
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
无论在扩大时或缩小窗口时都可以，因为求的是固定长度的子串。选择在缩小窗口时更新。
func findAnagrams(s string, p string) []int {
need, window := make(map[byte]int), make(map[byte]int)
for i := 0; i < len(p); i++ { // 初始化
if _, ok := need[p[i]]; ok {
need[p[i]]++
} else {
need[p[i]] = 1
}
}
left, right := 0, 0
valid := 0
ans := make([]int, 0)
for right < len(s) {
c := s[right]
right++
if _, ok := need[c]; ok {
if _, ok := window[c]; ok {
window[c]++
} else {
window[c] = 1
}
if need[c] == window[c] {
valid++
}
}
for valid == len(need) {
if right-left == len(p) {
ans = append(ans, left)
}
d := s[left]
left++
if _, ok := need[d]; ok {
if _, ok := window[d]; ok {
if need[d] == window[d] {
valid--
}
window[d]--
}
}
}
}
return ans
}
LeetCode题目：3. 无重复字符的最长子串
题目中包含关键字：时间复杂度O(n)、字符串、最小子串。可使用滑动窗口算法解决。
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
更新 window 中加入字符的个数，及当 window 中的某个字符个数 == 2时，更新 valid == false 。
2、什么条件下，窗口应该暂停扩大，开始移动_left_ 缩小窗口？
当 window 中的字符及个数 == 2时，即 valid == false 。
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
更新 window 中移出字符的个数，且判断 window 中移出字符个数是否 == 2 ，相等则 valid == true 。
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
在扩大窗口时，因为求的是最大子串。
func lengthOfLongestSubstring(s string) int {
if s == "" { // 当字符串为空时，返回0
return 0
}
window := make(map[byte]int)
left, right, max := 0, 0, 0
valid := true
for right < len(s) {
c := s[right]
right++
if _, ok := window[c]; !ok { // 初始化
window[c] = 0
}
window[c]++ // 累加
if window[c] == 2 { // 当出现重复字符时
valid = false
} else { // 否则累加不重复子串长度，并且判断是否当前最长
if max < right-left {
max = right - left
}
}
for valid == false {
d := s[left]
left++
if window[d] == 2 {
valid = true
}
window[d]--
}
}
return max
}
原文：https://www.cnblogs.com/liang24/p/13595458.html