滑动窗口也是一种双指针算法，但是滑动窗口特别强调窗口向一个方向滑动，看起来简单，但是却属于最难的一种双指针技巧，力扣上的题一般都是中等或困难难度。首要问题是识别什么样的问题需要滑动窗口解决，最常见的题型：子串问题。
子串问题 #
子串问题中，除了需要有 left 和 right 双指针，还需要计算（或比较）滑动窗口中的内容，常见的做法是维护一个（甚至更多）哈希表，需要更多哈希表的原因是一个维护窗口内的计数，另一个需要维护整个子串的计数器，用于互相比较。
因为每个字符都能够转换成 ASCII 码，除了哈希表有时维护一个长度为 26 的数组也可以（但要看题目是否只有小写字母），灵活考虑。比如 js 中虽然 map.size 很好用，但是给 map 的值做 ++ 运算却很麻烦，go 用 map 却很简单，所以哪个方便用哪个。
package main
import "fmt"
func main() {
m := make(map[string]int)
m["a"]++
fmt.Println(m["a"]) // 1
fmt.Println(m["c"]) // 0
}
滑动窗口解子串问题的核心思想：
- 维护左右两个指针，两指针之间就是窗口内容。
- 右指针向右滑动，直到窗口的子串符合满足题目要求。
- 停止右指针向右滑动，开始将左指针向右滑动，每次增加 left，都要更新窗口计数器内容。
- 重复 2 和 3，直到右指针到达尽头。
76. 最小覆盖子串（困难）这道题解的结构非常有代表性，而且比较难的地方也在于题目要求大小写都会包括，故只能用哈希表来保存窗口。
var minWindow = function (s, t) {
let need = new Map(),
window = new Map();
let left = 0,
right = 0;
let valid = 0,
start = 0;
let len = Infinity;
for (let i = 0; i < t.length; i++) {
let curr = t[i];
if (need.has(curr)) {
let v = need.get(curr);
need.set(curr, ++v);
} else {
need.set(curr, 1);
}
}
while (right < s.length) {
let c = s[right];
right++;
if (need.has(c)) {
if (window.has(c)) {
let v = window.get(c);
window.set(c, ++v);
} else {
window.set(c, 1);
}
if (window.get(c) == need.get(c)) {
valid++;
}
}
while (valid === need.size) {
if (right - left <= len) {
start = left;
len = right - left;
}
let d = s[left];
left++;
if (need.has(d)) {
let v = window.get(d);
if (window.get(d) === need.get(d)) {
valid--;
}
window.set(d, --v);
}
}
}
if (len === Infinity) {
return "";
} else {
return s.substr(start, len);
}
};
console.log(minWindow("ADOBECODEBANC", "ABC"));
567. 字符串的排列 和上面的结构一样，并且改为了 Array 实现。
var checkInclusion = function(s1, s2) {
let need = new Array(26).fill(0)
let window = new Array(26).fill(0)
let left = 0, right = 0
let ac = 'a'.charCodeAt()
for (let i = 0; i < s1.length; i ++) {
need[s1[i].charCodeAt() - ac] ++
}
while (right < s2.length) {
let curr = s2[right]
right++
if (need[curr.charCodeAt() - ac] > 0) {
window[curr.charCodeAt() - ac] ++
}
while(right - left >= s1.length) {
if (need.toString() === window.toString()) {
return true
}
let head = s2[left]
left++
if (need[head.charCodeAt()- ac] > 0) {
window[head.charCodeAt() - ac] --
}
}
}
return false
};
使用 Array 实现，个人感觉比 Map 要舒服点，也不需要 valid 计数了。
var findAnagrams = function(s, p) {
let need = new Array(26).fill(0)
let window = new Array(26).fill(0)
let left = 0, right = 0
let ac = 'a'.charCodeAt()
let ret = []
for (let i = 0; i < p.length; i++) {
need[p[i].charCodeAt() - ac]++
}
while(right<s.length) {
let curr = s[right]
right ++
if (need[curr.charCodeAt() - ac] > 0) {
window[curr.charCodeAt() - ac]++
}
if(right - left >= p.length) {
if (window.toString() === need.toString()) {
ret.push(left)
}
let head = s[left]
left ++
if (need[head.charCodeAt() - ac] > 0){
window[head.charCodeAt() - ac] --
}
}
}
return ret
};
另外两个数组可以考虑试图优化成一个数组，一加一减的思路。
总结一下必备的要素：
need符合要求的结果windows当前窗口的结果left和right移动的窗口两边
3. 无重复字符的最长子串（必会）
func lengthOfLongestSubstring(s string) int {
left := 0
right := 0
window := make(map[string]int)
ret := 0
for(right < len(s)) {
c := string(s[right])
right ++
window[c] ++
for (window[c] > 1) {
d := string(s[left])
left++
window[d] --
}
ret = max(ret, right - left)
}
return ret
}