0%

滑动窗口类题目(本章最后一题有惊喜)

一、综述

这类题在leetcode上,绝大部分都是难题,然后核心在于双指针技巧。

本文讲的例题从第3题覆盖到第727题。

二、滑动窗口思路讲解

在滑动窗口类型的问题中都会有两个指针。一个用于延伸现有窗口的 right指针,和一个用于收缩窗口的left 指针。在任意时刻,只有一个指针运动,而另一个保持静止。

本题的解法很符合直觉。我们通过移动right指针不断扩张窗口。当窗口包含全部所需的字符后,如果能收缩,我们就收缩窗口直到得到最小窗口。

答案是最小的可行窗口。

滑动窗口算法的思路是这样:

1、我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符)。

3、此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。

4、重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。

这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。

滑动窗口的抽象算法思想:

1
2
3
4
5
6
7
8
9
10
11
int left = 0, right = 0;

while (right < s.size()) {
window.add(s[right]);
right++;

while (valid) {
window.remove(s[left]);
left++;
}
}

使用滑动窗口解题的主要思想详细模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if not s:
return 0
from collections import defaultdict
lookup = defaultdict(int)
start,end = 0,0
max_len,counter = 0,0
while end < len(s):
if lookup(s[end]) > 0:
counter += 1
lookup[s[end]] += 1
end += 1
while counter > 0:
if lookup[s[start]] > 1:
counter -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len,end-start)
return max_len

三、例题讲解

1. 无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

思路:

这道题主要用到思路是:滑动窗口

什么是滑动窗口?

其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!

如何移动?

我们只要把队列的左边的元素移出就行了,直到满足题目要求!

一直维持这样的队列,找出队列出现最长的长度时候,求出解!

时间复杂度:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
left = 0
lookup = set()
n = len(s)
max_len,cur_len = 0,0
for i in range(n):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
max_len = max(max_len,cur_len)
lookup.add(s[i])
return max_len

2. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。

示例 1:

1
2
3
4
5
6
7
输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:

1
2
3
4
输入:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出:[]

思路:

这个就很简单了,我们可以想象成一直在维护一个窗口,右指针每次移动one_word长度,看是否满足题意了,如果不满足,则继续寻找,如果出现新词,则从左边开始删除,直到没有新词。

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
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
from collections import Counter
if not s or not words:
return []
one_word = len(words[0])
word_num = len(words)
n = len(s)
words = Counter(words)
res = []
for i in range(0,one_word):
cur_cnt = 0
left = right = i
cur_Counter = Counter()
while right+one_word <= n:
w = s[right:right + one_word]
right += one_word
cur_cnt += 1
cur_Counter[w] += 1
while cur_Counter[w] > words[w]:
left_w = s[left:left+one_word]
left += one_word
cur_Counter[left_w] -= 1
cur_cnt -= 1
if cur_cnt == word_num:
res.append(left)
return res

3. 最小覆盖子串

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。

示例:

1
2
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明:

  • 如果 S 中不存这样的子串,则返回空字符串 ""
  • 如果 S 中存在这样的子串,我们保证它是唯一的答案。

思路:

保存一个滑动窗口,end<len(s)来移动,count==0来判断是否覆盖完全,如果覆盖了,则从左边开始删除窗口数据,调整窗口大小,同时更新。

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
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
from collections import defaultdict
lookup = defaultdict(int)
for c in t:
lookup[c] += 1
start = end = 0
min_len = float('inf')
count = len(t)
res = ''
while end < len(s):
if lookup[s[end]] > 0:
count -= 1
lookup[s[end]] -= 1
end += 1
while count == 0:
if min_len>end - start:
min_len = end-start
res = s[start:end]
if lookup[s[start]] == 0:
count += 1
lookup[s[start]] += 1
start += 1
return res

4. 至多包含两个不同字符的最长子串

给定一个字符串 s ,找出 至多 包含两个不同字符的最长子串 t 。

示例 1:

1
2
3
输入: "eceba"
输出: 3
解释: t 是 "ece",长度为3。

示例 2:

1
2
3
输入: "ccaabbb"
输出: 5
解释: t 是 "aabbb",长度为5。

思路:

这道题思路就是模板思路,end<len(s)来右移动指针,cnt>2时来左移动指针。

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(object):
def lengthOfLongestSubstringTwoDistinct(self, s):
"""
:type s: str
:rtype: int
"""
from collections import defaultdict
lookup = defaultdict(int)
start = end = 0
max_len = 0
cnt = 0
while end < len(s):
if lookup[s[end]] == 0:
cnt += 1
lookup[s[end]] += 1
end +=1
while cnt > 2:
if lookup[s[start]] == 1:
cnt -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len,end-start)
return max_len

5. 至多包含K个不同字符的最长子串

记录

给定一个字符串 s ,找出 至多 包含 k 个不同字符的最长子串 T

示例 1:

1
2
3
输入: s = "eceba", k = 2
输出: 3
解释: 则 T 为 "ece",所以长度为 3。

示例 2:

1
2
3
输入: s = "aa", k = 1
输出: 2
解释: 则 T 为 "aa",所以长度为 2。

思路:

怎么说,这道题和上面一道题就是同一道题。。。用滑动窗口来做,就改了一个参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def lengthOfLongestSubstringKDistinct(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
from collections import defaultdict
lookup = defaultdict(int)
start = end = 0
max_len = 0
cnt = 0
while end < len(s):
if lookup[s[end]] == 0:
cnt += 1
lookup[s[end]] += 1
end +=1
while cnt > k:
if lookup[s[start]] == 1:
cnt -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len,end-start)
return max_len

6. 滑动窗口最大值

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。

返回滑动窗口最大值。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

注意:

你可以假设 k 总是有效的,1 ≤ k ≤ 输入数组的大小,且输入数组不为空。

进阶:

你能在线性时间复杂度内解决此题吗?

思路:

也是滑动窗口。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
start,end = 0,0
cnt = 0
res,tmp = [],[]
while end < len(nums):
cnt += 1
tmp.append(nums[end])
end += 1
while cnt > k:
tmp.remove(nums[start])
start += 1
cnt -= 1
if cnt == k:
res.append(max(tmp))
return res

7. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组如果不存在符合条件的连续子数组,返回 0。

示例:

1
2
3
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

思路:

就是标准的滑动窗口解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
if not nums or len(nums) == 0:
return 0
start,end = 0,0
tmp_sum = 0
res = float('inf')
while end < len(nums):
tmp_sum += nums[end]
end += 1
while tmp_sum >= s:
res = min(res,end-start)
tmp_sum -= nums[start]
start += 1
return 0 if res == float('inf') else res

8. 最小窗口子序列

给定字符串 S and T,找出 S 中最短的(连续)子串 W ,使得 TW子序列

如果 S 中没有窗口可以包含 T 中的所有字符,返回空字符串 ""。如果有不止一个最短长度的窗口,返回开始位置最靠左的那个。

示例 1:

1
2
3
4
5
6
输入:
S = "abcdebdde", T = "bde"
输出:"bcde"
解释:
"bcde" 是答案,因为它在相同长度的字符串 "bdde" 出现之前。
"deb" 不是一个更短的答案,因为在窗口中必须按顺序出现 T 中的元素。

注:

  • 所有输入的字符串都只包含小写字母。All the strings in the input will only contain lowercase letters.
  • S 长度的范围为 [1, 20000]
  • T 长度的范围为 [1, 100]

思路:

哈哈哈这个题尝试用滑动窗口不能解决,因为这是序列,不是子串,要考虑字符的前后顺序关系。所以下面的代码没有通过。得到的结果是’deb’

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
class Solution(object):
def minWindow(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
from collections import defaultdict
lookup = defaultdict(int)
for c in T:
lookup[c] += 1
start,end = 0,0
count = len(T)
min_len = float('inf')
res = ''
while end < len(S):
if lookup[S[end]] > 0:
count -= 1
lookup[S[end]] -= 1
end += 1
while count == 0:
if min_len > end - start:
min_len = end-start
res = S[start:end]
if lookup[S[start]] == 0:
count += 1
lookup[S[start]] += 1
start += 1
return res

正确思路是动态规划。

和76题的区别在于,一个是子串,一个是子序列。

DP(i,j)表示T[:i]和S[:j]满足题意时S中的起始index,也就是子串W的位置为S[index:j],index = DP(i,j)

所以就有递归方程:if T[i] == S[j]:DP(i,j) = DP(i-1,j-1) else:DP(i,j) = DP(i,j-1)

初始化:DP(i,j):if i == 0: DP(0,j) = j if j == 0: DP(i,0) = 0

由于题目要求的是子序列,所以需要得到起始位置和长度,还是最小窗口的。 也就是min(j-dp(len(T),j)),然后逐步更新即可。

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
class Solution(object):
def minWindow(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
m = len(T)
n = len(S)
dp = [[0] * (n+1) for _ in range(m+1)]
for j in range(n+1):
dp[0][j] = j + 1

for i in range(1,m+1):
for j in range(1,n+1):
if T[i-1] == S[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = dp[i][j-1]

start = 0
l = n+1
for j in range(1,n+1):
if dp[m][j] :
if j - dp[m][j] + 1 < l:
start = dp[m][j]-1
l = j - dp[m][j] + 1
return "" if l == n+1 else S[start:start+l]