Python算法-滑动窗口（Sliding Window）
滑动窗口
- 1 减少while循环
- 2 数组定长问题
3. 无重复字符的最长子串
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 哈希表+双指针
# 双指针
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
right = 0
result = 0
window = {}
while right < len(s):
if s[right] not in window:
window[s[right]] = 1
else:
window[s[right]] += 1
# 缩减窗口
while window[s[right]] > 1:
window[s[left]] -= 1
left += 1
# 维护一个最大值
result = max(result, right - left + 1)
right += 1
return result
209. 长度最小的子数组
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
# 双指针
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
right = 0
window_sum = 0
result = len(nums) + 1
while right < len(nums):
window_sum += nums[right]
while window_sum >= target:
result = min(result, right-left+1)
window_sum -= nums[left]
left += 1
right += 1
if result != len(nums) + 1:
return result
else:
return 0
713. 乘积小于K的子数组
给定一个正整数数组 nums和整数 k 。
请找出该数组内乘积小于 k 的连续的子数组的个数。
输入: 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的子数组。
输入: nums = [1,2,3], k = 0
输出: 0
# 双指针
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
left = 0
right = 0
window_sum = 1
result = 0
while right < len(nums):
window_sum *= nums[right]
# 区间左侧边界向右
while window_sum >= k:
window_sum /= nums[left]
left += 1
# 区间右侧边界向右
result += (right-left+1)
right += 1
return result
1343. 大小为 K 且平均值大于等于阈值的子数组数目
输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。
# 滑动窗口
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
left = 0
right = 0
window_sum = 0
result = 0
while right < len(arr):
# 更新窗口内数的求和
window_sum += arr[right]
if right - left + 1 >= k:
# 判断窗口内数的和与平均值的和
if window_sum >= k*threshold:
result += 1
# 窗口左边界向右移动
window_sum -= arr[left]
left += 1
# 窗口右边界向右移动
right += 1
return result
643. 子数组最大平均数 I
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
result = 1
count = 1
for i in range(len(nums)-1):
if nums[i] < nums[i+1]:
count += 1
else:
count = 1
result = max(result, count)
return result
674. 最长连续递增序列
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
result = 1
count = 1
for i in range(len(nums)-1):
if nums[i] < nums[i+1]:
count += 1
else:
count = 1
result = max(result, count)
return result
- 双指针
# 双指针
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
left = 0
right = 0
length = len(nums)
result = 0
for i in range(length):
if nums[i] > nums[right]:
right += 1
else:
left = i
right = i
result = max(result, right-left+1)
return result
1004. 最大连续1的个数 III
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = 0
right = 0
result = 0
count = 0
while right < len(nums):
# 右边界右移
if nums[right] == 0:
count += 1
right += 1
# 左边界右移
if count > k:
if nums[left] == 0:
count -= 1
left += 1
# 更新最大值
result = max(result, right-left)
return result
1423. 可获得的最大点数
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
# 使用固定长度的滑动窗口
# 由于只能从开头或末尾位置拿 k 张牌，则最后剩下的肯定是连续的 len(cardPoints) - k 张牌。
# 要求求出 k 张牌可以获得的最大收益，我们可以反向先求出连续 len(cardPoints) - k 张牌的最小点数。
# 则答案为 sum(cardPoints) - min_sum。
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
left = 0
right = 0
length = len(cardPoints)
card_sum = sum(cardPoints)
min_sum = card_sum
window_size = length - k # 窗口大小
window_sum = 0
if length == k:
return card_sum
while right < length:
window_sum += cardPoints[right]
if right - left + 1 >= window_size:
min_sum = min(min_sum, window_sum)
window_sum -= cardPoints[left]
left += 1
right += 1
return card_sum - min_sum
1052. 爱生气的书店老板
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意。
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
# 滑动窗口
# 窗口大小 X
# 固定长度的滑动窗口题目。我们可以维护一个窗口大小为 minutes 的滑动窗口。
# 使用 window_count 记录当前窗口内生气的顾客人数。
# 然后滑动求出窗口中最大顾客数，然后累加上老板未生气时的顾客数，就是答案。
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
left = 0
right = 0
result = 0
window_sum = 0
while right < len(customers):
# 求窗口内最多的生气顾客数
if grumpy[right] == 1:
window_sum += customers[right]
# 窗口左边界右移
if right - left + 1 > minutes:
if grumpy[left] == 1:
window_sum -= customers[left]
left += 1
right += 1
result = max(result, window_sum)
# print(result)
# 求没有生气的顾客数量
for i in range(len(customers)):
if grumpy[i] == 0:
result += customers[i]
return result
1456. 定长子串中元音的最大数目
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
# 定长窗口
class Solution:
def maxVowels(self, s: str, k: int) -> int:
hashmap = ['a','e','i','o','u']
left = 0
right = 0
count = 0
result = 0
while right < len(s):
if s[right] in hashmap:
count += 1
if right - left + 1 > k:
if s[left] in hashmap:
count -= 1
left += 1
result = max(result, count)
right += 1
return result
567. 字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
# 排列关系如何处理？
# 用 collections.Counter() 实现对数组中元素个数的统计
import collections
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
left = 0
right = 0
s1_count = collections.Counter(s1)
window_count = collections.Counter()
window_size = len(s1)
while right < len(s2):
window_count[s2[right]] += 1
# 窗口变小
if right - left + 1 >= window_size:
if window_count == s1_count:
return True
window_count[s2[left]] -= 1
if window_count[s2[left]] == 0:
del window_count[s2[left]]
left += 1
right += 1
return False
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
# 字典+滑动窗口
import collections
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# 创建数组p的字典
p_dict = collections.defaultdict(int)
for i in p:
p_dict[i] += 1
# 变量初始化
left = 0
right = 0
# 创建滑动窗口的字典
window_dict = collections.defaultdict(int)
window_size = len(p)
count = 0 # 统计相同字符的个数
result = []
# 滑动窗口实现
while right < len(s):
if s[right] in p_dict:
window_dict[s[right]] += 1
if window_dict[s[right]] == p_dict[s[right]]:
count += 1
# 窗口左边界右移
if right - left + 1 >= window_size:
# 如果窗口内元素形成的字典与目标数组的字典相等
if count == len(p_dict):
result.append(left)
# 还要考虑窗口左边界右移是否会移除目标元素
if s[left] in p_dict:
if window_dict[s[left]] == p_dict[s[left]]:
count -= 1
window_dict[s[left]] -= 1
left += 1
right += 1
return result
995. K 连续位的最小翻转次数（困难）
在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。
输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。
class Solution:
def minKBitFlips(self, nums: List[int], k: int) -> int:
result = 0
flip_count = 0
for i in range(len(nums)):
# 如果 i - k >= 0，并且 nums[i - k] == 2，需要缩小窗口，将翻转次数减一。
# （此时窗口范围为 [i - k + 1, i - 1]）
if i - k >= 0 and nums[i-k] == 2:
flip_count -= 1
# 如果 (flip_count + nums[i]) % 2 == 0，则说明 nums[i] 还需要再翻转一次，
# 将 nums[i] 标记为 2，同时更新窗口内翻转次数 flip_count 和答案最小翻转次数 ans。
if (flip_count + nums[i])%2 == 0:
if i + k > len(nums):
return -1
nums[i] = 2
flip_count += 1
result += 1
return result
例题
209：长度最小的子数组
输入：s = 7 , nums=[2,3,1,2,4,3]
输出：2 （找出该数组中满足其和 >= s 的长度最小的 连续子数组，返回其长度）
解释：子数组[4,3]是该条件下的长度最小的子数组
def findSub(s, nums):
if nums == None or len(nums) == 0:
return 0
res = len(nums) + 1
total = 0 # 子数组的和
i = 0
j = 0
while j < len(nums):
total = total + nums[j] # 右指针向右滑动
j = j + 1
while total >= s:
res = min(res, j-i) # 注意是 j - i
total = total - nums[i] # 左指针向右移动
i = i + 1
if res == len(nums) + 1: # 给定一个不可能的值，表示没找到
return 0
else:
return res
s = 7
nums=[2,3,1,2,4,3]
print(findSub(s, nums))
1456：定长字串中 元音字母 的最大数目
输入：s = 'abciiidef' k = 3（子串定长为3）
输出：3
解释：子字符串 'iii' 包含 3 个元音字母
def countSub(s, k):
if s == None or len(s) == 0 or len(s) < k:
return 0
# 元音字母哈希
hashset = {'a', 'e', 'i', 'o', 'u'}
res = 0
count = 0
for i in range(k): # 窗口为 k
if s[i] in hashset:
count += 1
res = max(res, count)
for i in range(k, len(s)):
if s[i-k] in hashset: # 窗口右移
count -= 1
if s[i] in hashset:
count += 1
res = max(res, count)
return res
s = 'abciiidef'
k = 3
print(countSub(s, k))
