# 滑动窗口思想

## 模板

```cpp
/* 滑动窗口算法框架 */
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++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}
```

需要变化的地方

* 1、右指针右移之后窗口数据更新
* 2、判断窗口是否要收缩
* 3、左指针右移之后窗口数据更新
* 4、根据题意计算结果

## 示例

[minimum-window-substring](https://leetcode-cn.com/problems/minimum-window-substring/)

> 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串

```go
func minWindow(s string, t string) string {
    // 保存滑动窗口字符集
    win := make(map[byte]int)
    // 保存需要的字符集
    need := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }
    // 窗口
    left := 0
    right := 0
    // match匹配次数
    match := 0
    start := 0
    end := 0
    min := math.MaxInt64
    var c byte
    for right < len(s) {
        c = s[right]
        right++
        // 在需要的字符集里面，添加到窗口字符集里面
        if need[c] != 0 {
            win[c]++
            // 如果当前字符的数量匹配需要的字符的数量，则match值+1
            if win[c] == need[c] {
                match++
            }
        }

        // 当所有字符数量都匹配之后，开始缩紧窗口
        for match == len(need) {
            // 获取结果
            if right-left < min {
                min = right - left
                start = left
                end = right
            }
            c = s[left]
            left++
            // 左指针指向不在需要字符集则直接跳过
            if need[c] != 0 {
                // 左指针指向字符数量和需要的字符相等时，右移之后match值就不匹配则减一
                // 因为win里面的字符数可能比较多，如有10个A，但需要的字符数量可能为3
                // 所以在压死骆驼的最后一根稻草时，match才减一，这时候才跳出循环
                if win[c] == need[c] {
                    match--
                }
                win[c]--
            }
        }
    }
    if min == math.MaxInt64 {
        return ""
    }
    return s[start:end]
}
```

[permutation-in-string](https://leetcode-cn.com/problems/permutation-in-string/)

> 给定两个字符串 **s1** 和 **s2**，写一个函数来判断 **s2** 是否包含 **s1** 的排列。

```go
func checkInclusion(s1 string, s2 string) bool {
    win := make(map[byte]int)
    need := make(map[byte]int)
    for i := 0; i < len(s1); i++ {
        need[s1[i]]++
    }
    left := 0
    right := 0
    match := 0
    for right < len(s2) {
        c := s2[right]
        right++
        if need[c] != 0 {
            win[c]++
            if win[c] == need[c] {
                match++
            }
        }
        // 当窗口长度大于字符串长度，缩紧窗口
        for right-left >= len(s1) {
            // 当窗口长度和字符串匹配，并且里面每个字符数量也匹配时，满足条件
            if match == len(need) {
                return true
            }
            d := s2[left]
            left++
            if need[d] != 0 {
                if win[d] == need[d] {
                    match--
                }
                win[d]--
            }
        }
    }
    return false
}
```

[find-all-anagrams-in-a-string](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/)

> 给定一个字符串 **s** 和一个非空字符串 **p**，找到 **s** 中所有是 **p** 的字母异位词的子串，返回这些子串的起始索引。

```go
func findAnagrams(s string, p string) []int {
    win := make(map[byte]int)
    need := make(map[byte]int)
    for i := 0; i < len(p); i++ {
        need[p[i]]++
    }
    left := 0
    right := 0
    match := 0
    ans:=make([]int,0)
    for right < len(s) {
        c := s[right]
        right++
        if need[c] != 0 {
            win[c]++
            if win[c] == need[c] {
                match++
            }
        }
        // 当窗口长度大于字符串长度，缩紧窗口
        for right-left >= len(p) {
            // 当窗口长度和字符串匹配，并且里面每个字符数量也匹配时，满足条件
            if right-left == len(p)&& match == len(need) {
                ans=append(ans,left)
            }
            d := s[left]
            left++
            if need[d] != 0 {
                if win[d] == need[d] {
                    match--
                }
                win[d]--
            }
        }
    }
    return ans
}
```

[longest-substring-without-repeating-characters](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)

> 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:
>
> 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

```go
func lengthOfLongestSubstring(s string) int {
    // 滑动窗口核心点：1、右指针右移 2、根据题意收缩窗口 3、左指针右移更新窗口 4、根据题意计算结果
    if len(s)==0{
        return 0
    }
    win:=make(map[byte]int)
    left:=0
    right:=0
    ans:=1
    for right<len(s){
        c:=s[right]
        right++
        win[c]++
        // 缩小窗口
        for win[c]>1{
            d:=s[left]
            left++
            win[d]--
        }
        // 计算结果
        ans=max(right-left,ans)
    }
    return ans
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
```

## 总结

* 和双指针题目类似，更像双指针的升级版，滑动窗口核心点是维护一个窗口集，根据窗口集来进行处理
* 核心步骤
  * right 右移
  * 收缩
  * left 右移
  * 求结果

## 练习

* [ ] [minimum-window-substring](https://leetcode-cn.com/problems/minimum-window-substring/)
* [ ] [permutation-in-string](https://leetcode-cn.com/problems/permutation-in-string/)
* [ ] [find-all-anagrams-in-a-string](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/)
* [ ] [longest-substring-without-repeating-characters](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://greyireland.gitbook.io/algorithm-pattern/suan-fa-si-wei/slide_window.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.