用于解决数组连续元素、字符串子串等问题。

滑动窗口对应left、right两个指针，指针中间区域成为窗口
窗口无非是两种操作：扩大或缩小。关键是何时缩小窗口

最小覆盖子串

最小覆盖子串
image.png

  1. 首先定义左右两个编辑指针，通常都是用作闭右开：[left, right)
  2. 定义服务函数，判断窗口满足条件
  3. 扩大窗口，直到窗口满足条件
  4. 缩小窗口，直到窗口不满足条件，记录窗口位置
  5. 选择窗口最小的一个作为结果返回 ```python def test(window, need): if len(window) < len(need):
    1.  return False
    for c, n in need.items():
    1.  if window.get(c, 0) < n:
    2.      return False
    return True

def minimum_substring(s, t): window = defaultdict(int) need = defaultdict(int) for c in t: need[c] += 1

  1. left, right = 0, 0
  2. result = []
  3. # 扩大窗口
  4. while right < len(s):
  5.     c = s[right]
  6.     right += 1
  7.     window[c] += 1
  8.     if test(window, need):
  9.         # 开始收缩窗口
  10.         while left < right:
  11.             c = s[left]
  12.             left += 1
  13.             window[c] -= 1
  14.             if !test(window, need):
  15.                 result.append(right-left + 1, left -1, right)
  16.                 break
  18. if not result:
  19.     return ''
  21. _, left, right = min(result)
  22. return s[left:right]

```

实战

最小覆盖子串
字符串的排列
找到字符串中所有字母异位词
无重复字符的最长子串