滑动窗口【基础算法精讲 03】

滑动窗口【基础算法精讲 03】滑动窗口即同向双指针209. 长度最小的子数组# 思路一先尽可能收缩再判断# while 还能缩且仍满足条件:# 缩# if 现在满足: 记录classSolution(object):defminSubArrayLen(self,target,nums): :type target: int :type nums: List[int] :rtype: int nlen(nums)ansn1left0mysum0forright,numinenumerate(nums):mysumnumwhilemysum-nums[left]target:mysum-nums[left]left1ifmysumtarget:ansmin(ans,right-left1)returnansifansnelse0# 思路二 先记录再收缩# while 满足条件:# 记录# 缩classSolution(object):defminSubArrayLen(self,target,nums): :type target: int :type nums: List[int] :rtype: int nlen(nums)ansn1left0mysum0forright,numinenumerate(nums):mysumnumwhilemysumtarget:ansmin(ans,right-left1)mysum-nums[left]left1returnansifansnelse0小节enumerate(iterable, start0)是 Python 内置函数用于同时获取索引和元素值避免手动维护计数器。fruits[apple,banana,cherry]# 默认从 0 开始fori,fruitinenumerate(fruits):print(i,fruit)# 0 apple# 1 banana# 2 cherry核心思路**滑动窗口双指针**利用单调性——数组元素为正窗口和随 right 增大而增大随 left 增大而减小目标找和 ≥ target 的最短连续子数组,因此双指针均单向移动不会回退。设计说明right窗口右边界逐个扩展left窗口左边界条件满足时收缩mysum维护窗口内元素和713. 乘积小于 K 的子数组classSolution(object):defnumSubarrayProductLessThanK(self,nums,k): :type nums: List[int] :type k: int :rtype: int # 注意k 没有正整数乘积1ifk1:return0ans0left0mul1forright,numinenumerate(nums):mul*numwhilemulk:mul//nums[left]left1# left到right之间的数乘积满足条件缩短后减少了数字一定满足ansright-left1returnans小节使用/浮点除法精度可能丢失应使用//或先判断k 1。k 1时没有子数组能满足乘积 k正整数最小乘积为 1应直接返回 0。核心思路滑动窗口 计数设计说明right扩展窗口右边界乘入新元素left收缩当乘积 ≥ k 时除以左边元素缩小乘积ans right - left 1以 right 结尾的所有满足条件的子数组个数3. 无重复字符的最长子串classSolution(object):deflengthOfLongestSubstring(self,s): :type s: str :rtype: int ans0charnumCounter()left0forright,cinenumerate(s):charnum[c]1whilecharnum[c]1:# 这里依次将left所指的元素的个数减一不一定正好是导致出现重复的元素charnum[s[left]]-1left1ansmax(ans,right-left1)returnans# 更简洁用 set 判断是否存在classSolution(object):deflengthOfLongestSubstring(self,s):char_setset()left0ans0forright,cinenumerate(s):whilecinchar_set:# 类似上述思路只是换成几何形式char_set.remove(s[left])left1char_set.add(c)ansmax(ans,right-left1)returnans# 最优用 dict 记录字符最新位置直接跳转 leftclassSolution(object):deflengthOfLongestSubstring(self,s):char_idx{}# 记录字符 - 最新下标left0ans0# 优化之处在于直接跳到重复字符的下一个位置减少不是导致重复元素的移动forright,cinenumerate(s):ifcinchar_idxandchar_idx[c]left:leftchar_idx[c]1# 直接跳到重复字符的下一个位置char_idx[c]right ansmax(ans,right-left1)returnans小节Counter()是 Pythoncollections模块中的类用于快速统计可迭代对象中元素的出现次数。fromcollectionsimportCounter# 统计字符串sabracadabracntCounter(s)# Counter({a: 5, b: 2, r: 2, c: 1, d: 1})# 统计列表nums[1,2,2,3,3,3]cntCounter(nums)# Counter({3: 3, 2: 2, 1: 1})核心思路滑动窗口 哈希计数设计说明right扩展窗口右边界逐个加入字符left收缩当窗口内出现重复字符时右移 left 直到无重复charnum(Counter)维护窗口内各字符的出现次数ans记录窗口的最大长度版本时间空间特点Counter 版O(n)O(字符集大小)通用但维护计数略冗余滑动窗口维护无重复字符区间right 扩展加入新字符出现重复时 left 收缩直到无重复记录最大窗口长度。set 版O(n)O(字符集大小)简洁只判存在性滑动窗口维护无重复字符区间right 扩展加入新字符出现重复时 left 收缩直到无重复记录最大窗口长度。dict 版O(n)O(字符集大小)最优left 直接跳转无需逐个移出字典记录字符最新下标遇到重复时直接让 left 跳到上次出现位置1无需逐个移出窗口内字符。关键是判断char_idx[c] left过滤掉窗口外的过时记录确保跳转正确性。这是滑动窗口的跳跃版将均摊复杂度从可能 O(n²) 降到严格 O(n)。3090. 每个字符最多出现两次的最长子字符串classSolution(object):defmaximumLengthSubstring(self,s): :type s: str :rtype: int ans0charnumCounter()left0forright,cinenumerate(s):charnum[c]1whilecharnum[c]2:# 这里依次将left所指的元素的个数减一不一定正好是导致出现重复的元素charnum[s[left]]-1left1ansmax(ans,right-left1)returnans# 优化 用 pos记录字符出现的前两次位置直接跳转left# 到导致不满足字符最多出现两次的元素的第一次出现的位置classSolution(object):defmaximumLengthSubstring(self,s):# 记录每个字符在窗口内的出现次数cnt[0]*26# 记录每个字符的出现位置用于快速找到第1次出现位置# pos是一个列表元素为列表的列表 即[[],[],...[]]pos[[]for_inrange(26)]left0ans0forright,cinenumerate(s):idxord(c)-ord(a)cnt[idx]1pos[idx].append(right)# 当 c 出现第3次left 直接跳到 c 第1次出现位置 1whilecnt[idx]2:first_pospos[idx][0]# c 的第1次出现位置# 移除 left 到 first_pos 之间的所有字符计数foriinrange(left,first_pos1):cnt[ord(s[i])-ord(a)]-1pos[ord(s[i])-ord(a)].pop(0)leftfirst_pos1ansmax(ans,right-left1)returnans小节[[] for _ in range(26)]用列表推导式创建 26 个独立的空列表分别存储 26 个字母的出现位置索引是处理固定小字符集时记录位置的常用技巧。核心思路滑动窗口维护字符频次 ≤ 22958. 最多 K 个重复元素的最长子数组classSolution(object):defmaxSubarrayLength(self,nums,k): :type nums: List[int] :type k: int :rtype: int ans0cnmCounter()left0forright,numinenumerate(nums):cnm[num]1whilecnm[num]k:cnm[nums[left]]-1left1ansmax(ans,right-left1)returnans小节滑动窗口维护元素频次right 扩展加入元素超过 k 次时 left 收缩直到满足条件记录最大窗口长度。每个元素最多进出窗口一次线性时间解决。核心思路滑动窗口 哈希计数2730. 找到最长的半重复子字符串classSolution(object):deflongestSemiRepetitiveSubstring(self,s): :type s: str :rtype: int nlen(s)ifn1:returnn left0ans1pair0# 窗口内相邻相同字符的对数forrightinrange(1,n):# 新加入的字符是否形成新的相邻相同对ifs[right]s[right-1]:pair1# 当相邻相同对超过1时收缩左边界whilepair1:ifs[left]s[left1]:pair-1left1# 更新最大长度ansmax(ans,right-left1)returnans小节注意边界情况字符串长度小于1题目限制的不是某个字符出现次数而是相邻相同对数 ≤ 1。核心思路滑动窗口 计数相邻相同对。right扩展时检查是否新增相邻相同对pair 1时left收缩直到只剩一对。核心是状态定义从字符频次转变为相邻相同对的数量实现 O(1) 空间的线性解法。1004. 最大连续1的个数 IIIclassSolution(object):deflongestOnes(self,nums,k): :type nums: List[int] :type k: int :rtype: int nlen(nums)ifnk:returnn ans0left0maxkkforright,numinenumerate(nums):ifnum!1:maxk-1whilemaxk0:ifnums[left]0:maxk1left1ansmax(ans,right-left1)returnans核心思路滑动窗口维护 0 的个数把翻转 k 个 0转化为窗口内最多包含 k 个 0right 扩展遇到 0 则消耗翻转机会0 的个数超过 k 时 left 收缩归还机会记录最大窗口长度。核心是用剩余翻转次数maxk作为窗口收缩的触发条件实现 O(1) 空间的线性解法2962. 统计最大元素出现至少 K 次的子数组classSolution(object):defcountSubarrays(self,nums,k): :type nums: List[int] :type k: int :rtype: int maxnummax(nums)left0# 满足最大元素至少出现K次的最大元素的下标countans0forright,numinenumerate(nums):ifnummaxnum:count1whilecountk:ifnums[left]maxnum:count-1left1ansleftreturnans核心思路滑动窗口 计数最大元素。right扩展计数maxnumcount k时left收缩到刚好不满足。关键技巧ans left以right结尾的满足条件的子数组起始位置有left个可选。设计说明maxnum数组中的最大元素固定值count窗口内maxnum的出现次数right扩展窗口右边界遇到maxnum则count 1left收缩当count k时右移left直到count kans left关键以right结尾的满足条件的子数组个数2302. 统计得分小于 K 的子数组数目classSolution(object):defcountSubarrays(self,nums,k):nlen(nums)left0mysum0# 窗口内元素和ans0forright,numinenumerate(nums):mysumnum# 收缩当得分 k 时左边界右移while(right-left1)*mysumk:mysum-nums[left]left1# 以 right 结尾的满足条件的子数组个数# 起始位置可以是 left, left1, ..., right# 共 (right - left 1) 个ansright-left1returnans小节利用正数性质实现 O(n) 线性计数。窗口满足条件时其内部所有以right结尾的更短子数组长度变小mysum变小也满足。所以ans right - left 1一次性统计所有以right结尾的合法子数组。核心思路滑动窗口 正数单调性设计说明right扩展窗口右边界加入新元素累加和left收缩当长度 × 和 k时右移 left 减小窗口mysum维护窗口[left, right]内的元素和关键更新ans right - left 11658. 将 x 减到 0 的最小操作数(建议复习)classSolution(object):defminOperations(self,nums,x):totalsum(nums)targettotal-x# 如果 target 0说明全部移除也不够iftarget0:return-1# 滑动窗口找和为 target 的最长子数组left0mysum0max_len-1# 标记是否找到forright,numinenumerate(nums):mysumnumwhilemysumtarget:mysum-nums[left]left1ifmysumtarget:max_lenmax(max_len,right-left1)# 如果没找到返回 -1ifmax_len-1:return-1# 操作次数 总长度 - 中间保留长度returnlen(nums)-max_len小节问题转换核心思路逆向思维 滑动窗口题目要求从数组两端移除元素使和等于 x求最少操作次数。逆向转换找数组中间一段连续子数组使其和等于total - x且长度最长。3795. 不同元素和至少为 K 的最短子数组长度(建议复习)classSolution(object):defminLength(self,nums,k):nlen(nums)ansn1left0cntCounter()# 窗口内元素频次unique_sum0# 不同元素的和forright,numinenumerate(nums):cnt[num]1ifcnt[num]1:# 第一次出现unique_sumnum# 收缩窗口whileunique_sumk:ansmin(ans,right-left1)# 移出 leftleft_numnums[left]cnt[left_num]-1ifcnt[left_num]0:# 该元素不再在窗口中unique_sum-left_num# 减少内存消耗delcnt[left_num]left1returnansifansnelse-1小节滑动窗口维护不同元素和用 Counter 记录窗口内元素频次只有元素首次出现时才加入unique_sum移出时只有频次降为 0 才从unique_sum减去。当不同元素和 ≥ k 时收缩窗口记录最短长度。76. 最小覆盖子串(特别难)class Solution(object): def minWindow(self, s, t): need Counter(t) # t 中各字符需要的频次 missing len(t) # 还需要匹配的字符总数 left 0 min_len float(inf) min_start 0 for right, c in enumerate(s): # 扩展窗口 if need[c] 0: # c 是 t 中需要的字符 missing - 1 # 对所有字符进行处理包括不在t中出现的字符 # 不出现的字符初始值为0t中出现的字符初始值为正数 need[c] - 1 # 收缩窗口当所有字符都匹配够时 while missing 0: # 更新最小窗口 if right - left 1 min_len: min_len right - left 1 min_start left # 移出 left 字符对所有的字符进行处理 # 对于非t中出现的字符归还后值为负数或者零最终回到零 # 对于t中出现的字符归还后大于零说明把需要的字符归回啦小于零目前的字串仍能覆盖t need[s[left]] 1 # 归还一个需求 if need[s[left]] 0: # 如果归还后还需要说明移出的是关键字符 missing 1 left 1 return s[min_start:min_start min_len] if min_len ! float(inf) else 小节python3中支持Counter直接比较进行覆盖判断Python 2Python 3Counter 比较不支持支持报错位置cnt_s cnt_t行为异常正常实际现象while条件异常导致left一直增加到越界正常核心思路滑动窗口 需求计数。用Counter记录每个字符的剩余需求missing跟踪还需匹配的字符总数。窗口满足条件时收缩找最小不满足时扩展。核心是用need[c]的正负零区分还需要、“有冗余”、“刚好够”精确处理重复字符的匹配问题。