前言
在这个专题，我们主要讨论 sliding window 的具体用法。
针对很多类型的问题都可以使用 sliding window，比如说在一个字符串中找到最长的不重复子串，或者是在一个数组中找到最长的连续子数组等等。
我们简单介绍一下 sliding window 的模版：
def slidingWindow(s: str):
window = defaultdict(int)
left, right = 0, 0
while right < len(s):
cur_right = s[right]
window[cur_right] += 1
right += 1
# 进行窗口内数据的一系列更新
...
# debug 输出的位置
print(f"window: [{left}, {right})")
# 判断左侧窗口是否要收缩
while left < right and window needs shrink:
cur_left = s[left]
window[cur_left] -= 1
if window[cur_left] == 0:
del window[cur_left]
left += 1
# 进行窗口内数据的一系列更新
...这个模版的核心思想是：
-
- 先不断地增加 right 指针扩大窗口
-
- 当窗口包含了 t 的所有字符后，开始不断地收缩 left 指针，直到得到最小窗口
基础题
3. Longest Substring Without Repeating Characters
这道题的描述是找到最长的不重复子串，我们可以使用 sliding window 来解决。
test cases:
Input: s = "abcabcbb"
Output: 3
Input: s = "bbbbb"
Output: 1
Input: s = "pwwkew"
Output: 3这道题的思路是，我们使用一个 window 来存储当前的子串，然后不断地增加 right 指针来扩大窗口，直到窗口中出现了重复的字符，此时我们就需要收缩 left 指针来缩小窗口，直到窗口中不再有重复的字符。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
window = defaultdict(int)
left, right = 0, 0
res = 0
while right < len(s):
cur_right = s[right]
window[cur_right] += 1
right += 1
while window[cur_right] > 1: # 如果 window 中 cur_right 字符的数量大于 1，说明窗口中出现了重复的字符
cur_left = s[left]
window[cur_left] -= 1
left += 1
res = max(res, right - left)
return res复杂度分析：
- 时间复杂度：O(n)，原因是我们需要遍历整个字符串。
- 空间复杂度：O(n)，因为我们使用了一个 window 来存储当前的子串。
76. Minimum Window Substring
这道题的描述是找到最小的包含 t 的子串，我们可以使用 sliding window 来解决。
test cases:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Input: s = "a", t = "a"
Output: "a"这道题的思路是，我们使用一个 window 来存储当前的子串，然后不断地增加 right 指针来扩大窗口，直到窗口中包含了 t 的所有字符，此时我们就需要收缩 left 指针来缩小窗口，直到窗口中不再包含 t 的所有字符。
class Solution:
def minWindow(self, s: str, t: str) -> str:
left, right = 0, 0
min_start, min_length = None, float("inf")
window = collections.Counter()
target = collections.Counter(t)
valid = 0 # 记录 window 中已经有多少字符符合要求了
while right < len(s):
cur_right = s[right]
window[cur_right] += 1
if window[cur_right] == target[cur_right]:
valid += 1 # 如果 window 中 cur_right 字符的数量符合要求了，那么 valid += 1
right += 1
while left <= right and valid >= len(target): # 如果 window 中包含了所有字符，那么就开始收缩 left 指针
if right - left < min_length: # 如果当前的窗口大小更小，则更新 min_length
min_start = left
min_length = right - left
cur_left = s[left]
if cur_left in target: # 如果 window 中 cur_left 字符的数量不再符合要求了，那么 valid -= 1
if window[cur_left] == target[cur_left]:
valid -= 1
window[cur_left] -= 1
left += 1
return s[min_start: min_start + min_length] if min_length != float("inf") else ""复杂度分析：
- 时间复杂度：O(n)，原因是我们需要遍历整个字符串。
- 空间复杂度：O(n)，因为我们使用了一个 window 来存储当前的子串。
209. Minimum Size Subarray Sum
这道题的描述是找到最小的连续子数组，使得子数组的和大于等于 s，我们可以使用 sliding window 来解决。
test cases:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Input: s = 4, nums = [1,4,4]
Output: 1
Input: s = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0这道题的思路是，我们使用一个 window 来存储当前的子串，然后不断地增加 right 指针来扩大窗口，直到窗口中的和大于等于 s，此时我们就需要收缩 left 指针来缩小窗口，直到窗口中的和小于 s。
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
left, right = 0, 0
res = float("inf")
window = 0 # 记录 window 中的和
while right < len(nums):
cur_right = nums[right]
window += cur_right
right += 1
while window >= s:
res = min(res, right - left)
cur_left = nums[left]
window -= cur_left
left += 1
return res if res != float("inf") else 0复杂度分析：
- 时间复杂度：O(n)，原因是我们需要遍历整个数组。
- 空间复杂度：O(1)，因为我们使用了一个 window 来存储当前的子串。
567. Permutation in String
这道题的描述是判断 s2 中是否包含 s1 的排列，我们可以使用 sliding window 来解决。
test cases:
Input: s1 = "ab", s2 = "eidbaooo"
Output: True
Input: s1= "ab", s2 = "eidboaoo"
Output: False这道题的思路是，我们使用一个 window 来存储当前的子串，然后不断地增加 right 指针来扩大窗口，直到窗口中包含了 s1 的所有字符，此时我们就需要收缩 left 指针来缩小窗口，直到窗口中不再包含 s1 的所有字符。
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
left, right = 0, 0
window = collections.Counter()
target = collections.Counter(s1)
valid = 0 # 记录 window 中已经有多少字符符合要求了
while right < len(s2):
cur_right = s2[right]
window[cur_right] += 1
right += 1
if cur_right in target:
if window[cur_right] == target[cur_right]:
valid += 1 # 如果 window 中 cur_right 字符的数量符合要求了，那么 valid += 1
while right - left >= len(s1): # 如果 window 中包含了所有字符，那么就开始收缩 left 指针
if valid == len(target): # 如果当前的窗口大小等于 s1 的长度，则说明找到了一个排列
return True
cur_left = s2[left]
if cur_left in target: # 如果 window 中 cur_left 字符的数量不再符合要求了，那么 valid -= 1
if window[cur_left] == target[cur_left]:
valid -= 1
window[cur_left] -= 1
left += 1
return False复杂度分析：
- 时间复杂度：O(n)，原因是我们需要遍历整个字符串。
- 空间复杂度：O(n)，因为我们使用了一个 window 来存储当前的子串。
438. Find All Anagrams in a String
这道题的描述是找到 s 中所有 p 的排列，我们可以使用 sliding window 来解决。
test cases:
Input: s: "cbaebabacd" p: "abc"
Output: [0, 6]
Input: s: "abab" p: "ab"
Output: [0, 1, 2]这道题的思路是，我们使用一个 window 来存储当前的子串，然后不断地增加 right 指针来扩大窗口，直到窗口中包含了 p 的所有字符，此时我们就需要收缩 left 指针来缩小窗口，直到窗口中不再包含 p 的所有字符。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
left, right = 0, 0
window = collections.Counter()
target = collections.Counter(p)
valid = 0 # 记录 window 中已经有多少字符符合要求了
res = []
while right < len(s):
cur_right = s[right]
window[cur_right] += 1
if cur_right in target:
if window[cur_right] == target[cur_right]:
valid += 1
right += 1
while right - left >= len(p): # 如果 window 中包含了所有字符，那么就开始收缩 left 指针
if valid == len(target): # 如果当前的窗口大小等于 p 的长度，则说明找到了一个排列
res.append(left)
cur_left = s[left]
if cur_left in target: # 如果 window 中 cur_left 字符的数量不再符合要求了，那么 valid -= 1
if window[cur_left] == target[cur_left]:
valid -= 1
window[cur_left] -= 1
left += 1
return res复杂度分析：
- 时间复杂度：O(n)，原因是我们需要遍历整个字符串。
- 空间复杂度：O(n)，因为我们使用了一个 window 来存储当前的子串。
高级题
30. Substring with Concatenation of All Words
这道题的描述是找到 s 中所有 words 的排列，我们可以使用 sliding window 来解决。
test cases:
Input: s: "barfoothefoobarman" words: ["foo", "bar"]
Output: [0, 9]
Input: s: "wordgoodgoodgoodbestword" words: ["word", "good", "best", "word"]
Output: []这道题的思路是，我们使用一个 window 来存储当前的子串，然后不断地增加 right 指针来扩大窗口，直到窗口中包含了 words 的所有字符，此时我们就需要收缩 left 指针来缩小窗口，直到窗口中不再包含 words 的所有字符。
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
word_len = len(words[0])
all_word_len = word_len * len(words)
target = collections.Counter(words)
res = []
for i in range(word_len):
word_dict = collections.defaultdict(int)
left = right = i
while right < len(s):
word = s[right:right + word_len]
word_dict[word] += 1
if right - left + word_len == all_word_len:
if word_dict == target:
res.append(left)
word = s[left:left + word_len]
word_dict[word] -= 1
if word_dict[word] == 0:
del word_dict[word]
left += word_len
right += word_len
return res复杂度分析：
- 时间复杂度：O(nm)，原因是我们需要遍历整个字符串, n 是 s 的长度，m 是 words 的长度。
- 空间复杂度：O(n)，因为我们使用了一个 window 来存储当前的子串。
[2444. Count Subarrays With Fixed Bounds] (https://leetcode.com/problems/count-subarrays-with-fixed-bounds/)
未完待续
Comments NOTHING