滑动窗口方法

滑动窗口方法（Sliding Window Technique）是指在数据结构（通常是数组或字符串）中移动固定或可变大小的窗口，以基于连续元素子集有效地解决问题的技术。

Abstract

1. 使用兩個指針（left, right）表示一個窗口，left 指針表示窗口的起始位置，right 指針表示窗口的結束位置。
2. 隨著右指針逐步移動，擴大窗口，當遇到重複字符時，按顺序縮小窗口，直到窗口内不再有重复字符。

说明

1. 目前窗口中含有字符 X。当 right 移动遇到下一个字符 X 时，left 滑动到第一个 X 的下一个位置，使当前窗口中不再有重复字符；
2. left 滑动前窗口中的字符串与已经保存的最长子串对比/替换；

Time Complexity

一般来说这些问题可以使用嵌套循环在 O(N2) 时间复杂度中解决，使用滑动窗口可以在 O(N) 时间复杂度中解决这些问题。

应用

• 最长无重复子串
• 最小覆盖子串（所有给定字符都至少出现一次）
• 子串和问题