当前位置: 首页> 教育> 锐评 > 3 滑动窗口

3 滑动窗口

时间:2025/7/10 21:34:02来源:https://blog.csdn.net/qq_28611929/article/details/140013489 浏览次数:0次

滑动窗口是一种常用的数据结构和算法思想,广泛应用于处理数组或序列中的连续片段问题。它的核心特点是窗口的大小可以动态调整,但总保持一个固定大小,通过在序列上“滑动”来检查不同的子序列。以下是滑动窗口的一些典型应用场景:

  1. 最大/最小值查找:在一系列数据中,寻找连续子序列的最大值或最小值,如股票价格最高点、最低点等。

  2. 子数组问题

    • 和的最值:如找到一个大小为k的子数组,使其和最大或最小。
    • 平均值最值:寻找具有最大或最小平均值的连续子数组。
    • 子数组问题计数:统计满足特定条件(如和大于某值)的子数组数量。
  3. 字符串处理

    • 字符计数:如判断一个字符串中是否存在长度为k的子串包含所有唯一字符。
    • 无重复字符的最长子串长度:经典的滑动窗口应用,如LeetCode上的问题"Longest Substring Without Repeating Characters"。
    • 字符串匹配问题:如寻找所有长度为k且匹配特定模式的子串。

滑动窗口的优势在于它可以在O(N)的时间复杂度内解决很多问题,其中N是序列的长度,通过一次遍历就能完成大部分计算,非常适合处理大规模数据流或高效遍历数组的需求。

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

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

示例 1:

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

示例 2:

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

示例 3:

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

思想:最长 无重复,什么是个无冲出,当然要有对比,先设定一个容器暂时用来存储当前最长无重复的子串,然后往右滑动,

1 没有重复,扩容器;

2 有重复,容积缩;

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 固定一个容器 setcontainer = []length = 0for i in s:if i not in container:# 扩展容器container.append(i)length = max(length, len(container))else:# 容器缩进,并把当前的元素加入index = container.index(i)container = container[index+1:]container.append(i)return length         

 438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

使用列表: 

1 判断两个序列是否是异位词;
2 滑动窗口;走一步判断一步;
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:# len_p = len(p)len_s = len(s)if len_p>len_s:return []p = sorted(p)results = []for i in range(len_s-len_p+1):if s[i] not in p:continueif sorted(s[i:i+len_p])==p:results.append(i)return results

使用字典 :

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:# len_p = len(p)len_s = len(s)if len_p>len_s:return []# 对比的字典p_d = {}for i in p:if i in p_d:p_d[i]+=1else:p_d[i] = 1# 滑动窗口的字典  t_dict = {}for i in s[:len_p]:if i in t_dict:t_dict[i] += 1else:t_dict[i] =1results = []for i in range(len_p,len_s):if t_dict==p_d:results.append(i-len_p)top = s[i-len_p]# 滑动1个# 删除元素if t_dict[top]>1:t_dict[top]-=1else:t_dict.pop(top)# 添加元素if s[i] in t_dict:t_dict[s[i]]+=1else:t_dict[s[i]]=1if t_dict==p_d:results.append(len_s-len_p)return results

关键字:3 滑动窗口

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: