滑动窗口是一种常用的数据结构和算法思想,广泛应用于处理数组或序列中的连续片段问题。它的核心特点是窗口的大小可以动态调整,但总保持一个固定大小,通过在序列上“滑动”来检查不同的子序列。以下是滑动窗口的一些典型应用场景:
最大/最小值查找:在一系列数据中,寻找连续子序列的最大值或最小值,如股票价格最高点、最低点等。
子数组问题:
- 和的最值:如找到一个大小为k的子数组,使其和最大或最小。
- 平均值最值:寻找具有最大或最小平均值的连续子数组。
- 子数组问题计数:统计满足特定条件(如和大于某值)的子数组数量。
字符串处理:
- 字符计数:如判断一个字符串中是否存在长度为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