【2025-02-12】 基础算法：滑动窗口
📝前言说明： ●本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，主要跟随B站博主灵茶山的视频进行学习，专栏中的每一篇文章对应B站博主灵茶山的一个视频 ●题目主要为B站视频内涉及的题目以及B站视频中提到的“课后作业”。 ●文章中的理解仅为个人理解。 ●文章中的截图来源于B站博主灵茶山，如有侵权请告知。
🎬个人简介：努力学习ing 📋本专栏：python刷题专栏 📋其他专栏：C语言入门基础以及python入门基础 🎀CSDN主页 愚润求学
一，什么是滑动窗口
滑动窗口是：通过动态调整窗口的左右边界来避免重复计算，从而降低时间复杂度。其核心思想是维护一个窗口，通过移动右边界扩展窗口、移动左边界收缩窗口，找到满足条件的解。（窗口的状态始终要满足条件）
滑动窗口前提： 1，操作的窗口是连续子数组 2，有单调性，即可以根据窗口来退出其他的子数组是否满足条件，如：若窗口满足条件，则窗口内的子数组也满足条件
做题要点： 1，明确窗口要满足的条件 2，明确左右指针的移动方向（根据条件），以及如何维护窗口满足条件 3，明确是何种“单调性”，进行题目要求求解
●视频题目题号： 209，3，713 ●课后作业题号： 2958,，2730，2779，1004，2962，2302，76
二，视频题目
1，209. 长度最小的子数组
●题目：
●题解：
如：对于2,3,1,2，> 7，所以尝试收缩左端点，但是3,1,2< 7，所以不行，只能扩展右端点，得到新窗口2,3,1,2,4，再收缩新窗口，最多收缩到1,2,4，然后又右扩展，以此类推
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
s = 0
ans = n + 1
left = 0
for right, x in enumerate(nums): # right: 索引，x: nums[right]
s += x
while s - nums[left] >= target:
s -= nums[left]
left += 1
if s >= target:
ans = min(ans, right-left+1)
return ans if ans <= n else 02，713. 乘积小于 K 的子数组
题目：
题解：
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
# 若右端点为r，左端点为l，且从l到r所有元素的乘积小于k，则以右端点r为基础，向左扩展，可以得到的连续子数组的数目有r-l+1个(即这些数组有包含右端点)
if k <= 1:
return 0
left = 0
ans = 0
prod = 1
for right, x in enumerate(nums):
prod *= x
while prod >= k:
prod /= nums[left]
left += 1
ans += right - left + 1
return ans 3，3. 无重复字符的最长子串
题目：
题解：
用哈希表记录字符出现的次数，若重复，则一定是新计入的字符重复出现了
Counter()：自动将输入的可迭代对象转换为一个哈希表，其中键是元素，值是该元素出现的次数。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
ans = 0
cnt = Counter() # hasmap char: int
for right, x in enumerate(s):
cnt[x] += 1
while cnt[x] > 1:
cnt[s[left]] -= 1
left += 1
ans = max(ans, right-left+1)
return ans三，课后作业
1，2958. 最多 K 个重复元素的最长子数组
题目：
题解：
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
n = len(nums)
left = 0
ans = 0
cnt = Counter()
for right, x in enumerate(nums):
cnt[x] += 1
while cnt[x] > k:
cnt[nums[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans2，2730. 找到最长的半重复子字符串
题目：
题解：
class Solution:
def longestSemiRepetitiveSubstring(self, s: str) -> int:
# 1，窗口状态（条件）：里面有的连续相同的字符的对数
# 2，满足条件：右端点扩展，不满足：左端点收缩，收缩到只有一对连续相同的字符
ans, left, same = 1, 0, 0
for right in range(1, len(s)):
same += s[right] == s[right-1]
if same > 1:
left += 1
while s[left] != s[left-1]:
left += 1
same -= 1
ans = max(ans, right - left + 1)
return ans3，2779. 数组的最大美丽值
题目：（难点在找窗口条件）
题解： 由于选的是子序列（不要求连续），且变换只与元素本身和k值有关，与位置无关，所以元素顺序对答案没有影响，可以先对数组排序。
也就是子数组中：最大数-最小数<=2k，代表子数组内所有元素都可以换成同一个数。【这就是窗口的条件】
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
nums.sort()
left, ans = 0, 0
for right in range(0, len(nums)):
while nums[right] - nums[left] > 2*k:
left += 1
ans = max(ans, right-left+1)
return ans4，1004. 最大连续 1 的个数
题目：
题解：
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
# 题意转换成：窗口内至多有k个0
left, ans, zero = 0, 0, 0
for right in range(0, len(nums)):
zero += nums[right] == 0
if zero > k:
while nums[left] == 1:
left += 1
left += 1
zero -= 1
ans = max(ans, right-left+1)
return ans5，2962. 统计最大元素出现至少 K 次的子数组
题目：
题解：
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
# 条件：让窗口内恰好有k个最大值，则以右端和窗口为基础，计算子数组个数
mx = max(nums)
ans, left, count = 0, 0, 0
for right in range(0,len(nums)):
count += nums[right] == mx
while count == k:
if nums[left] == mx:
count -= 1
left += 1
ans += left # 即：当满足条件以后，每一个right都能对应left个子数组（left-1-0+1==left）
return ans6，2302. 统计得分小于 K 的子数组数目
题目：
题解：
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
# 在本题：若窗口满足条件，因为都是正数，所以窗口内的子数组的得分肯定比窗口的得分更小（元素少了，长度短了）
left, ans = 0, 0
sum = 0
for right in range(0, len(nums)):
lens = right - left + 1
sum = sum + nums[right]
while lens * sum >= k:
sum -= nums[left]
left += 1
lens -= 1
ans += lens
return ans7，1658. 将 x 减到 0 的最小操作数
题目：
题解：
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
# 窗口条件：若原数组的各元素之和为s，则只需：窗口的元素之和 == s - x
# 即变成：找到子数组内各元素之和等于s - x的最长的子数组
n = len(nums)
target = sum(nums) - x
if target < 0: return -1
left, s = 0, 0
ans = -1
for right, x in enumerate(nums):
s += x
while s > target:
s -= nums[left]
left += 1
if s == target:
ans = max(ans, right - left + 1)
return n - ans if ans != -1 else -18，76. 最小覆盖子串
题目：
题解：
由Counter创建的hasmap也是可以直接比较的
class Solution:
def minWindow(self, s: str, t: str) -> str:
# 窗口要满足的条件：涵盖：t中每个字符出现的次数 <= s中子字符串中字符出现的次数
cnt_s = Counter()
cnt_t = Counter(t)
left = 0
ans = inf
ans_left, ans_right = -1, len(s)
for right, c in enumerate(s):
cnt_s[c] += 1
while cnt_s >= cnt_t:
if right - left + 1 < ans_right - ans_left + 1: # 满足条件的解，更新最短子串
ans_left, ans_right = left, right
cnt_s[s[left]] -= 1
left += 1
return "" if ans_left < 0 else s[ans_left: ans_right + 1] # 切片腾讯云开发者
