滑动窗口解题模板

题目要求

类型 1: 给定两个字符串 s 和 t,找满足某种变化规律的字串/最大字串/最大字串长度等。

类型 2:给定字符串 s,查找满足某种条件的最大/最小窗口。

解题模板

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def slidingWindowTemplate(s, t):
# 定义其他变量,存储结果,存储判断条件等变量
begin = end = 0

while f(): # case 1: slide end
# do something
end += 1
while g(): # case 2: slide begin
# do something
begin += 1
# meet some condition

模版变形:

  • 前后指针同步移动可以简化为一层循环
  • exactly(K) = atMost(K) - atMost(K-1)

案例应用

案例 1: Leetcode 424

Medium: Longest Repeating Character Replacement

给定一个字符串 s 和整数 k,求 s 变换 k 次后得到的最长重复子串是多长。其中变换规律是:每次操作可以将一个字符变化成任意字符。重复字符串是指所有字符都相同的字符串。

end 每次滑动要做啥:

累计 s[end] 出现的次数。如果 s[end] 出现次数大于了窗口中最大重复次数,则更新最大重复次数。如果窗口长度大于 k + max_count 则需要移动 begin 指针。

begin 指针移动要做啥:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
if not s:
return 0
begin = end = 0
map = collections.defaultdict(int)
max_count = max_len = 0

while end < len(s):
c = s[end]
map[c] += 1
max_count = max(max_count, map[c])

end += 1

while end - begin > k + max_count:
b = s[begin]
map[b] -= 1
begin += 1

max_len = max(max_len, end - begin)

return max_len

案例 2:Max Consecutive Ones III

Medium: https://leetcode.com/problems/max-consecutive-ones-iii/solution/

给定一个只有 0 和 1 的数组 A 和一个操作次数 K,每次操作可以从 0 变成 1,求在 k 次操作下最大子数组的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def longestOnes(self, A: List[int], k: int) -> int:
begin = end = 0
max_len = 0
nums_one = 0

while end < len(A):
if A[end] == 1:
nums_one += 1

end += 1
while end - begin > nums_one + k:
if A[begin] == 1:
nums_one -= 1
begin += 1

max_len = max(max_len, end - begin)

return max_len

案例 3:Grumpy Bookstore Owner

Medium: https://leetcode.com/problems/grumpy-bookstore-owner/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def maxSatisfied(self, cus: List[int], gru: List[int], x: int) -> int:
init_sum = max_sum = 0
n = len(cus)
for i in range(n):
if gru[i] == 0:
init_sum += cus[i]

begin = end = 0

while end < n:
if gru[end] == 1:
init_sum += cus[end]
# [begin, end]
while end - begin == x:
if gru[begin] == 1:
init_sum -= cus[begin]
begin += 1

max_sum = max(max_sum, init_sum)
end += 1 # 考虑清楚下次 end 移动之前要做哪些事情

return max_sum

案例 4: Longest Substring Without Repeating Characters

Medium: https://leetcode.com/problems/longest-substring-without-repeating-characters/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
map = collections.defaultdict(int)
counter = 0
begin = end = 0

max_len = 0

while end < len(s):
e = s[end]
map[e] += 1
if map[e] > 1: # e is repeating
counter += 1 # counter is number of repeating

end += 1

while counter > 0: # has repeated number
b = s[begin]
if map[b] > 1:
counter -= 1
map[b] -= 1

begin += 1

max_len = max(max_len, end - begin)

return max_len

案例 5: Get Equal Substrings Within Budget

Medium: https://leetcode.com/problems/get-equal-substrings-within-budget/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def equalSubstring(self, s: str, t: str, cost: int) -> int:
begin = end = 0
max_len = 0

while end < len(s):
cost -= abs(ord(s[end]) - ord(t[end]))
end += 1

while cost < 0:
cost += abs(ord(s[begin]) - ord(t[begin]))
begin += 1

max_len = max(end - begin, max_len)

return max_len

案例 6:Permutation in String

Medium: https://leetcode.com/problems/permutation-in-string/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
d = collections.Counter(s1)
counter = len(d)

begin = end = 0

while end < len(s2):
e = s2[end]
if e in d:
d[e] -= 1
if d[e] == 0:
counter -= 1
end += 1

while counter == 0:
b = s2[begin]
if b in d:
d[b] += 1
if d[b] > 0:
counter += 1
if end - begin == len(s1):
return True

begin += 1

return False

案例 7: Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
def minWindow(self, s: str, t: str) -> str:
map = collections.Counter(t)

found = False
begin = end = 0
counter = len(map)
start = 0
min_len = len(s)

while end < len(s):
e = s[end]
if e in map:
map[e] -= 1
if map[e] == 0:
counter -= 1
end += 1

while counter == 0:
found = True
b = s[begin]
if b in map:
map[b] += 1
if map[b] > 0:
counter += 1

if end - begin < min_len:
min_len = end - begin
start = begin

begin += 1

return s[start: start + min_len] if found else ""

本文标题:滑动窗口解题模板

文章作者:Pylon, Syncher

发布时间:2019年10月24日 - 19:10

最后更新:2023年09月26日 - 10:09

原始链接:https://0x400.com/fundamental/algorithm/lc-sliding-window-template/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。