滑动窗口法 python
时间: 2023-09-01 13:12:48 浏览: 64
滑动窗口法(Sliding Window)是一种常见的数组或字符串问题的解决方法。它通常用于在给定数组或字符串中寻找一些连续的区间,这些区间需要满足一定的条件。滑动窗口法的基本思想是维护一个窗口,通过调整窗口的起始位置和结束位置来寻找符合条件的区间。
下面是一个使用滑动窗口法解决字符串问题的例子,该问题是要找到一个字符串中最短的包含所有指定字符的子串。
```python
def min_window(s: str, t: str) -> str:
# 初始化字典
needs = {}
for c in t:
needs[c] = needs.get(c, 0) + 1
# 初始化窗口和计数器
left, right, cnt = 0, 0, len(t)
# 初始化最小覆盖子串的起始位置和长度
start, length = 0, float('inf')
while right < len(s):
# 如果当前字符在需要的字符中,计数器减一
if s[right] in needs:
needs[s[right]] -= 1
if needs[s[right]] >= 0:
cnt -= 1
right += 1
# 如果计数器为0,则找到了一个符合要求的子串
while cnt == 0:
# 更新最小覆盖子串的起始位置和长度
if right - left < length:
start = left
length = right - left
# 如果当前字符在需要的字符中,计数器加一
if s[left] in needs:
needs[s[left]] += 1
if needs[s[left]] > 0:
cnt += 1
left += 1
return '' if length == float('inf') else s[start:start + length]
```
在这个例子中,我们首先初始化了一个字典 `needs`,用于存储需要的字符及其出现次数。然后,我们初始化了窗口的起始位置和结束位置为0,并将计数器 `cnt` 初始化为需要的字符的总数。接下来,我们开始移动右指针 `right`,并在遍历字符串的过程中不断更新字典 `needs` 和计数器 `cnt`,直到找到一个符合要求的区间。一旦找到符合要求的区间,我们开始移动左指针 `left`,直到不能满足条件为止。在移动左指针的过程中,我们不断更新最小覆盖子串的起始位置和长度。最后,我们返回最小覆盖子串,如果不存在符合要求的子串,则返回空字符串。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)