# Sliding Window

{% embed url="<https://leetcode.com/tag/sliding-window/>" %}

* when sliding window: 在一个长string/list里面找符合条件的substring/sublist
* how: 用双指针标记一个滑动的window来代表当前的子字符串，不断检验子字符串是否符合要求。
* 要求的时间复杂度往往是O(n)，空间复杂度往往是常数级的。
* sliding window 很少见easy题目，但不是sliding window本身有多难，基本都是难在变量的维护、指针移动条件的判断等细节，题目变化比较多。

## 要素：

1. 左指针移动条件\[, 停止移动条件]
2. 记录结果条件

## 模版：

```python
def slidingWindow(A, B=None):
    map = defaultdict(int) # 描述window的hashmap
    res = [] # 记录最终要返回的结果，有时是计数 or sth other
    count = 0 # 条件值：用来维护 {window是否满足要求}
    
    # 有时候可以对主串str或者题目的要求做预处理，通常是算frequency
    
    l, r = 0, 0 # 左右指针，有时寻找的substring长度固定，那就可以只用一个指针（隐式双指针）
    while r < len(A): # 一般是一直移动右指针
        map[A[r]] += 1 # 处理右侧新进字符
        
        # 根据窗口的变更结果来改变条件值
        if (map[A[r]] == ...):
        ...
         
        # 移动左指针的条件（有时是window满足要求就停，有时是不满足要求才停）
        while (count == K):
            if (...):
                res.append(A[l:r+1])
            
            # 处理左边界跳出字符，移动左指针    
            map[A[l]] -= 1
            l += 1
        
        # 移动右指针
        r += 1
     
    return res
```

## 题目整理：

### 窗口大小不变：

{% content-ref url="sliding-window/438.-find-all-anagrams-in-a-string" %}
[438.-find-all-anagrams-in-a-string](https://xuqiangwen1994.gitbook.io/practice/sliding-window/438.-find-all-anagrams-in-a-string)
{% endcontent-ref %}

{% content-ref url="sliding-window/567.-permutation-in-string" %}
[567.-permutation-in-string](https://xuqiangwen1994.gitbook.io/practice/sliding-window/567.-permutation-in-string)
{% endcontent-ref %}

{% content-ref url="sliding-window/1100.-find-k-length-substrings-with-no-repeated-characters" %}
[1100.-find-k-length-substrings-with-no-repeated-characters](https://xuqiangwen1994.gitbook.io/practice/sliding-window/1100.-find-k-length-substrings-with-no-repeated-characters)
{% endcontent-ref %}

### 窗口大小可变：

{% content-ref url="sliding-window/3.-longest-substring-without-repeating-characters" %}
[3.-longest-substring-without-repeating-characters](https://xuqiangwen1994.gitbook.io/practice/sliding-window/3.-longest-substring-without-repeating-characters)
{% endcontent-ref %}

{% content-ref url="sliding-window/76.-minimum-window-substring" %}
[76.-minimum-window-substring](https://xuqiangwen1994.gitbook.io/practice/sliding-window/76.-minimum-window-substring)
{% endcontent-ref %}

{% content-ref url="sliding-window/159.-longest-substring-with-at-most-two-distinct-characters" %}
[159.-longest-substring-with-at-most-two-distinct-characters](https://xuqiangwen1994.gitbook.io/practice/sliding-window/159.-longest-substring-with-at-most-two-distinct-characters)
{% endcontent-ref %}

{% content-ref url="sliding-window/340.-longest-substring-with-at-most-k-distinct-characters" %}
[340.-longest-substring-with-at-most-k-distinct-characters](https://xuqiangwen1994.gitbook.io/practice/sliding-window/340.-longest-substring-with-at-most-k-distinct-characters)
{% endcontent-ref %}

{% content-ref url="sliding-window/424.-longest-repeating-character-replacement" %}
[424.-longest-repeating-character-replacement](https://xuqiangwen1994.gitbook.io/practice/sliding-window/424.-longest-repeating-character-replacement)
{% endcontent-ref %}

{% content-ref url="sliding-window/992.-subarrays-with-k-different-integers" %}
[992.-subarrays-with-k-different-integers](https://xuqiangwen1994.gitbook.io/practice/sliding-window/992.-subarrays-with-k-different-integers)
{% endcontent-ref %}

### 特殊数据结构：

{% content-ref url="sliding-window/239.-sliding-window-maximum" %}
[239.-sliding-window-maximum](https://xuqiangwen1994.gitbook.io/practice/sliding-window/239.-sliding-window-maximum)
{% endcontent-ref %}
