滑动窗口方法：修订间差异

来自牛奶河Wiki
跳到导航 跳到搜索
（创建页面，内容为“滑动窗口方法（Sliding Window Technique）是指在数据结构（通常是数组或字符串）中移动固定或可变大小的窗口，以基于连续元素子集有效地解决问题的技术。 ===Abstract=== #使用兩個指針（left, right）表示一個窗口，left 指針表示窗口的起始位置，right 指針表示窗口的結束位置。 #隨著右指針逐步移動，擴大窗口，當遇到重複字符時，按顺序縮小窗口，直到…”）
 
无编辑摘要
第8行： 第8行：
#目前窗口中含有字符 X。当 right 移动遇到下一个字符 X 时，left 滑动到第一个 X 的下一个位置，使当前窗口中不再有重复字符；
#目前窗口中含有字符 X。当 right 移动遇到下一个字符 X 时，left 滑动到第一个 X 的下一个位置，使当前窗口中不再有重复字符；
#left 滑动前窗口中的字符串与已经保存的最长子串对比/替换；
#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===
===Time Complexity===

2024年12月4日 (三) 14:25的版本

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

Abstract

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

说明

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

Max=OOXOOO, window=OOXOOO, MaxLength=5

#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) 时间复杂度中解决这些问题。

应用

  • 最长无重复子串
  • 最小覆盖子串（所有给定字符都至少出现一次）
  • 子串和问题
取自“https://mwbbs.eu.org/wiki/index.php?title=滑动窗口方法&oldid=2922”