查看“滑动窗口方法”的源代码

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

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

===说明===
#目前窗口中含有字符 X。当 right 移动遇到下一个字符 X 时，left 滑动到第一个 X 的下一个位置，使当前窗口中不再有重复字符；
#left 滑动前窗口中的字符串与已经保存的最长子串对比/替换；
{| class="wikitable"
|+#1
!left
!
!
!
!
!right
!
!
|-
|O
|O
|X
|O
|O
|O
|X
|O
|}
Max=OOXOOO, window=OOXOOO, MaxLength=5
{| class="wikitable"
|+#2
!
!
!
!left
!
!
!right
!
|-
|O
|O
|X
|O
|O
|O
|X
|O
|}
Max=OOXOOO, window=OOOX, MaxLength=5

以上图例中，O 代表任何字符，在上文中，显然除了最后一个 O，其他所有的 O 都不重复。

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

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

[[分类:Develop]]
[[分类:Algorithm]]