滑动窗口算法总结
滑动窗口算法总结
滑动窗口概念
滑动窗口是一种解决数组(或字符串)的子序列问题的通用方法,特别适合处理连续子数组或子串的问题。它通过维护一个可变大小的"窗口",在线性时间内解决原本需要嵌套循环的问题,从而将时间复杂度从O(n²)降低到O(n)。
基本思想:
- 维护一个"窗口",这个窗口包含了当前正在考虑的元素序列
- 窗口有两个边界:左边界(left)和右边界(right)
- 通过移动这两个边界来"滑动"窗口,从而遍历所有可能的子序列
滑动窗口的工作方式:
- 初始化左右指针,通常都指向序列的开始位置
- 右指针向右移动,扩大窗口,直到窗口满足某个条件
- 当条件满足时,记录结果,然后左指针向右移动,缩小窗口,直到条件不再满足(用while循环)
- 重复步骤2和3,直到右指针到达序列末尾
滑动窗口的适用场景
滑动窗口算法特别适合解决以下类型的问题:
-
寻找满足特定条件的连续子数组或子串
- 最大/最小长度的子数组,其和为k
- 不含重复字符的最长子串
- 包含特定字符的最短子串
-
需要在线性时间内解决的子序列问题
- 固定大小窗口的最大/最小值
- 满足特定条件的变长窗口
-
需要维护窗口内元素某种状态的问题
- 窗口内的最大/最小值
- 窗口内的元素种类数
- 窗口内元素的频率统计
滑动窗口的类型
1. 固定大小的滑动窗口
- 窗口大小固定不变
- 适用于求解固定长度子数组的问题
2. 可变大小的滑动窗口
- 窗口大小根据条件动态调整
- 适用于求解满足特定条件的最长/最短子数组
滑动窗口算法模板
固定窗口大小的模板:
public void slidingWindowFixed(int[] nums, int k) {
int n = nums.length;
// 初始化窗口
for (int i = 0; i < k; i++) {
// 处理窗口内的元素
}
// 滑动窗口
for (int i = k; i < n; i++) {
// 添加新元素
// 移除旧元素
// 处理当前窗口
}
}
可变窗口大小的模板:
public void slidingWindowVariable(int[] nums) {
int left = 0;
int right = 0;
int n = nums.length;
while (right < n) {
// 扩大窗口
// 更新窗口内的状态
while (/* 窗口需要收缩的条件 */) {
// 缩小窗口
// 更新窗口内的状态
left++;
}
// 更新结果
right++;
}
}
滑动窗口的应用实例
例1:无重复字符的最长子串
问题:给定一个字符串,找出其中不含有重复字符的最长子串的长度。
思路:使用滑动窗口和HashSet记录窗口中的字符。
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<>();
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
例2:长度为K的子数组最大和
问题:给定一个整数数组和一个整数k,找出长度为k的连续子数组的最大和。
思路:使用固定大小的滑动窗口。
public int maxSumSubarray(int[] nums, int k) {
int n = nums.length;
int maxSum = 0;
int windowSum = 0;
// 初始化第一个窗口
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
maxSum = windowSum;
// 滑动窗口
for (int i = k; i < n; i++) {
windowSum = windowSum + nums[i] - nums[i - k]; // 添加新元素,移除旧元素
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
例3:最小覆盖子串
问题:给你一个字符串S、一个字符串T,请在字符串S里面找出包含T所有字母的最小子串。
思路:使用可变大小的滑动窗口和HashMap记录窗口中字符的频率。
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
// 统计t中字符的频率
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0; // 已经满足条件的字符数量
int start = 0, len = Integer.MAX_VALUE; // 记录最小覆盖子串的起始位置和长度
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 更新窗口内数据
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 当所有字符都满足条件时,尝试缩小窗口
while (valid == need.size()) {
// 更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
// 更新窗口内数据
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
例4:找到所有字母异位词
问题:给定两个字符串s和p,找到s中所有p的异位词的起始索引。异位词指字母相同,但排列不同的字符串。
思路:使用固定大小的滑动窗口和数组记录字符频率。
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s == null || s.length() == 0 || p == null || p.length() == 0) {
return result;
}
int[] charCount = new int[26]; // 假设只有小写字母
// 统计p中字符的频率
for (char c : p.toCharArray()) {
charCount[c - 'a']++;
}
int left = 0, right = 0;
int count = p.length(); // 需要匹配的字符数
while (right < s.length()) {
// 如果当前字符在p中,减少需要匹配的字符数
if (charCount[s.charAt(right) - 'a'] > 0) {
count--;
}
// 减少对应字符的计数(可能为负,表示多余的字符)
charCount[s.charAt(right) - 'a']--;
right++;
// 当窗口大小等于p的长度时,检查是否找到异位词
if (right - left == p.length()) {
if (count == 0) {
result.add(left);
}
// 恢复左指针对应的字符计数
if (charCount[s.charAt(left) - 'a'] >= 0) {
count++;
}
charCount[s.charAt(left) - 'a']++;
left++;
}
}
return result;
}
滑动窗口算法的优化技巧
-
使用合适的数据结构:
- 使用HashSet/HashMap快速判断元素是否存在
- 使用双端队列(Deque)维护窗口内的最大/最小值
-
避免不必要的计算:
- 增量更新窗口状态,而不是每次重新计算
- 记录关键状态(如有效字符数量)避免重复检查
-
直接跳跃:
- 在某些情况下,可以直接将左指针跳到特定位置,而不是一步步移动
滑动窗口与其他算法的结合
滑动窗口算法常常与其他技术结合使用:
- 哈希表:用于快速查找和频率统计
- 双指针:滑动窗口本身就是双指针的一种特殊形式
- 前缀和:结合前缀和可以快速计算窗口内的元素和
- 单调队列:用于在O(1)时间内获取窗口内的最大/最小值
总结
滑动窗口是一种强大的算法技巧,它通过巧妙地维护和更新窗口状态,将许多原本需要O(n²)时间的子数组问题优化到O(n)时间。掌握滑动窗口技巧,对于解决数组、字符串的连续子序列问题非常有帮助。
关键要点:
- 识别问题是否适合使用滑动窗口
- 确定窗口的扩张和收缩条件
- 正确维护窗口内的状态
- 在适当的时机更新结果
本文是原创文章,采用 CC BY-NC-ND 4.0 协议,完整转载请注明来自 程序员小刘
评论
匿名评论
隐私政策
你无需删除空行,直接评论以获取最佳展示效果