LeetCode刷题:不定长滑动窗口专题
求最长/最大
3.无重复字符的最长子串
给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
思路：
使用滑动窗口，需要注意的是窗口左边往右缩小时是为了满足题目条件，一旦满足条件就停止，而窗口右边是正常的滑动。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
sets = set()
left = 0
for i in range(len(s)):
while s[i] in sets:
sets.remove(s[left])
left += 1
sets.add(s[i])
ans = max(ans, len(sets))
return ans
3090.每个字符最多出现两次的最长子字符串
给你一个字符串s，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。
示例 1：
输入： s = “bcbbbcba”
输出： 4
解释：
以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。
思路：
就是上一题的升级版
实现:
class Solution:
def maximumLengthSubstring(self, s: str) -> int:
sets = defaultdict(int)
ans = 0
left = 0
for i in range(len(s)):
while sets[s[i]] >= 2:
sets[s[left]] -= 1
left += 1
sets[s[i]] += 1
ans = max(ans, i - left + 1)
return ans
2831.找出最长等值子数组（未做出）
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
子数组 是数组中一个连续且可能为空的元素序列。
示例 1：
输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：最优的方案是删除下标 2 和下标 4 的元素。
删除后，nums 等于 [1, 3, 3, 3] 。
最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。
可以证明无法创建更长的等值子数组。
思路：
分组+滑动窗口，比如nums = [1,3,2,3,1,3]，我们可以把1，2，3分为三组，然后每次按组来遍历，看是否能将其他多余的元素删除，如果不超过k则更新等值子数组的长度。(参考灵神)
实现：
class Solution:
def longestEqualSubarray(self, nums: List[int], k: int) -> int:
pos_lists = defaultdict(list)
for i, x in enumerate(nums):
pos_lists[x].append(i)
ans = 0
for pos in pos_lists.values():
left = 0
for right, p in enumerate(pos):
while p - pos[left] - (right - left) > k:
left += 1
ans = max(ans,right - left + 1)
return ans
求最短/最小
209.长度最小的子数组
给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其总和大于等于target的长度最小的子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度**。**如果不存在符合条件的子数组，返回0。
思路
直接使用滑动窗口，每往右扩一次，就需要检查是否可以将左端点往右移动以找到满足题目条件的最子数组。
实现：
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
sum = 0
ans =len(nums)
count = 0
for i in range(len(nums)):
sum += nums[i]
count += 1
while sum - nums[left] >= target:
sum -= nums[left]
left += 1
count -= 1
if sum >= target:
ans = min(ans,count)
if ans == len(nums) and target > sum:
return 0
return ans
76.最小覆盖子串
给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
思路：
可以参考209题的做法，我们先滑动窗口右移，再从左边不断缩小窗口，找到最小的子串，这题我们需要注意的就是如何使用哈希表判断子串涵盖t的所有字符串。
注意我们判断哈希表是否涵盖可以直接使用cnt_s >= cnt_t。
class Solution:
def minWindow(self, s: str, t: str) -> str:
def set_contain(t_cnt: set, s_cnt: set) ->bool:
is_contain = True
for x in t_cnt:
if s_cnt[x] < t_cnt[x]:
is_contain = False
return is_contain
t_cnt = Counter(t)
s_cnt = Counter()
left = 0
ans_left = -1
ans_right = len(s)
for i, c in enumerate(s):
s_cnt[c] += 1
while set_contain(t_cnt,s_cnt):
if i - left < ans_right - ans_left:
ans_left = left
ans_right = i
s_cnt[s[left]] -= 1
left += 1
return s[ans_left:ans_right+1] if ans_left != -1 else ""
优化：
用一个变量 less 维护目前子串中有 less 种字母的出现次数小于 t 中字母的出现次数。
class Solution:
def minWindow(self, s: str, t: str) -> str:
ans_left, ans_right = -1, len(s)
cnt = defaultdict(int) # 比 Counter 更快
for c in t:
cnt[c] += 1
less = len(cnt) # 有 less 种字母的出现次数 < t 中的字母出现次数
left = 0
for right, c in enumerate(s): # 移动子串右端点
cnt[c] -= 1 # 右端点字母移入子串
if cnt[c] == 0:
# 原来窗口内 c 的出现次数比 t 的少，现在一样多
less -= 1
while less == 0: # 涵盖：所有字母的出现次数都是 >=
if right - left < ans_right - ans_left: # 找到更短的子串
ans_left, ans_right = left, right # 记录此时的左右端点
x = s[left] # 左端点字母
if cnt[x] == 0:
# x 移出窗口之前，检查出现次数，
# 如果窗口内 x 的出现次数和 t 一样，
# 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少
less += 1
cnt[x] += 1 # 左端点字母移出子串
left += 1
return "" if ans_left < 0 else s[ans_left: ans_right + 1]
2904.最短且字典序最小的美丽子字符串
给你一个二进制字符串s和一个正整数k。
如果s的某个子字符串中1的个数恰好等于k，则称这个子字符串是一个美丽子字符串。
令len等于最短美丽子字符串的长度。
返回长度等于len且字典序最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。
对于相同长度的两个字符串a和b，如果在a和b出现不同的第一个位置上，a中该位置上的字符严格大于b中的对应字符，则认为字符串a字典序大于字符串b。
- 例如，
"abcd"的字典序大于"abcc"，因为两个字符串出现不同的第一个位置对应第四个字符，而d大于c。
示例 1：
输入：s = "100011001", k = 3
输出："11001"
解释：示例中共有 7 个美丽子字符串：
1. 子字符串 "100011001" 。
2. 子字符串 "100011001" 。
3. 子字符串 "100011001" 。
4. 子字符串 "100011001" 。
5. 子字符串 "100011001" 。
6. 子字符串 "100011001" 。
7. 子字符串 "100011001" 。
最短美丽子字符串的长度是 5 。
长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。
思路：
维护一个滑动窗口，然后不断收缩找到最短美丽字符串，需要注意字典序最小的答案，直接用比较法就好了。
实现：
class Solution:
def shortestBeautifulSubstring(self, s: str, k: int) -> str:
if s.count('1') < k:
return ""
ans = s
left = 0
cnt_1 = 0
ss = ""
for right, x in enumerate(s):
cnt_1 += int(x)
while cnt_1 - int(s[left]) >= k:
cnt_1 -= int(s[left])
left += 1
if cnt_1 == k:
ss = s[left:right + 1]
if len(ss) < len(ans) or ss < ans and len(ss) == len(ans):
ans = ss
return ans
求子数组个数
一般要写 ans += left。
滑动窗口的内层循环结束时，右端点固定在 right，左端点在 0,1,2,…,left−1 的所有子数组（子串）都是合法的，这一共有 left 个。
1358.包含所有三种字符的子字符串数目
给你一个字符串s，它只包含三种字符a,b和c。
请你返回a，b和c都至少出现过一次的子字符串数目。
示例 1：
输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
思路：
利用哈希表存储a,b,c的个数，然后构建滑动窗口，如果满足条件就移动左端点，直到不满足条件，此时ans += left，left就是以right为右端点的子串数。
实现：
from collections import Counter
class Solution:
def numberOfSubstrings(self, s: str) -> int:
ans = 0
left = 0
n = len(s)
cnt_s = Counter("abc")
cnt_t = Counter()
for right, p in enumerate(s):
cnt_t[p] += 1
while cnt_t >= cnt_s:
cnt_t[s[left]] -= 1
left += 1
ans += left
return ans
if __name__ == "__main__":
s = "acbbcac"
solution = Solution()
print(solution.numberOfSubstrings(s))
2537.统计好子数组的数目
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。
思路：
延续上一题的思路，重点在于如何判断数组是好数组。
实现：
class Solution:
def countGood(self, nums: List[int], k: int) -> int:
cnt_g = Counter()
ans = 0
left = 0
pairs = 0
for right, p in enumerate(nums):
pairs += cnt_g[p]
cnt_g[p] += 1
while pairs >= k:
pairs -= cnt_g[nums[left]] - 1
cnt_g[nums[left]] -= 1
left += 1
ans += left
return ans
越短越合法
一般要写 ans += right - left + 1。
滑动窗口的内层循环结束时，右端点固定在right，左端点在left,left+1,…,right的所有子数组（子串）都是合法的，这一共有right−left+1 个。
713.乘积小于 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
实现：
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
ans = left = 0
s = 1
for right, p in enumerate(nums):
s *= p
while s >= k and left <= right:
s /= nums[ left]
left += 1
ans += right - left + 1
return ans
2762.不间断子数组
给你一个下标从0开始的整数数组nums。nums的一个子数组如果满足以下条件，那么它是不间断的：
i，i+1，…，j表示子数组中的下标。对于所有满足i<=i1,i2<=j的下标对，都有0<=|nums[i1]-nums[i2]|<=2。
请你返回不间断子数组的总数目。
子数组是一个数组中一段连续非空的元素序列。
示例 1：
输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8 。
除了这些以外，没有别的不间断子数组。
思路：
滑动窗口，需要注意的就是如何存储和获取窗口数组的最大最小值。我们可以使用哈希表来实现，因为最多只涉及到3个数，而且可以直接使用max和min函数获取最大最小值。
实现：
class Solution:
def continuousSubarrays(self, nums: List[int]) -> int:
ans = left = 0
sets = Counter()
for right, p in enumerate(nums):
sets[p] += 1
while max(sets) - min(sets) > 2:
sets[nums[left]] -= 1
if sets[nums[left]] == 0:
del sets[nums[left]]
left += 1
ans += right - left + 1
return ans
恰好型滑动窗口
例如，要计算有多少个元素和恰好等于𝑘的子数组，可以把问题变成：
- 计算有多少个元素和≥𝑘的子数组。
- 计算有多少个元素和𝑘，也就是 ≥𝑘+1 的子数组。
答案就是元素和≥𝑘的子数组个数，减去元素和≥𝑘+1的子数组个数。这里把>转换成≥，从而可以把滑窗逻辑封装成一个函数f，然后用 f(k) - f(k + 1) 计算，无需编写两份滑窗代码。
总结：「恰好」可以拆分成两个「至少」，也就是两个「越长越合法」的滑窗问题。
注：也可以把问题变成≤k减去≤k−1（两个至多）。可根据题目选择合适的变形方式。
注：也可以把两个滑动窗口合并起来，维护同一个右端点 right 和两个左端点 left1和 left2，我把这种写法叫做三指针滑动窗口。
930.和相同的二元子数组
给你一个二元数组nums，和一个整数goal，请你统计并返回有多少个和为goal的非空子数组。
子数组是数组的一段连续部分。
示例 1：
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
思路：
将恰好拆分成两个至少，然后直接套用越长越合的公式。
实现：
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
def sliding_window(nums: List[int], goal: int) -> int:
ans = left = 0
sum = 0
for right, p in enumerate(nums):
sum += p
while left <= right and sum >= goal:
sum -= nums[left]
left += 1
ans += left
return ans
return sliding_window(nums, goal) - sliding_window(nums, goal + 1)
3306.元音辅音字符串计数 II
给你一个字符串word和一个非负整数k。
返回 word 的 子字符串中，每个元音字母（'a'、'e'、'i'、'o'、'u'至少出现一次，并且恰好 包含k个辅音字母的子字符串的总数。
示例 1：
**输入：**word = “aeioqq”, k = 1
**输出：**0
解释：
不存在包含所有元音字母的子字符串。
思路：
与上题类似，但是难度要高一些，因为满足条件并不简单构造，我开始是打算使用哈希表构建一个元音字母表，如果滑动窗口的哈希表大于等于元音字母表，那么就满足第一个条件，第二个条件只好用一个count变量来计数，但是这样的实现超过了时间限制.
最后做了一些优化。
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
def s(word: str, k: int) -> int:
ans = left = 0
cnt_f = 0
cnt_y = 0
cnt_w = Counter()
for right, p in enumerate(word):
if p in "aeiou":
cnt_w[p] += 1
else:
cnt_f += 1
while len(cnt_w)== 5 and cnt_f >= k:
if word[left] in "aeiou":
cnt_w[word[left]] -= 1
if cnt_w[word[left]] == 0:
del cnt_w[word[left]]
else:
cnt_f -= 1
left += 1
ans += left
return ans
return s(word, k) - s(word, k + 1)
优化二
把两个滑动窗口合并成一个。我一般把这种滑窗叫做三指针滑窗。
class Solution:
def countOfSubstrings(self, word: str, k: int) -> int:
cnt_vowel1 = defaultdict(int)
cnt_vowel2 = defaultdict(int)
cnt_consonant1 = cnt_consonant2 = 0
ans = left1 = left2 = 0
for b in word:
if b in "aeiou":
cnt_vowel1[b] += 1
cnt_vowel2[b] += 1
else:
cnt_consonant1 += 1
cnt_consonant2 += 1
while len(cnt_vowel1) == 5 and cnt_consonant1 >= k:
out = word[left1]
if out in "aeiou":
cnt_vowel1[out] -= 1
if cnt_vowel1[out] == 0:
del cnt_vowel1[out]
else:
cnt_consonant1 -= 1
left1 += 1
while len(cnt_vowel2) == 5 and cnt_consonant2 > k:
out = word[left2]
if out in "aeiou":
cnt_vowel2[out] -= 1
if cnt_vowel2[out] == 0:
del cnt_vowel2[out]
else:
cnt_consonant2 -= 1
left2 += 1
ans += left1 - left2
return ans