滑动窗口（Sliding Window）是一种高效的算法技巧，通过维护一个动态变化的区间（窗口）来避免重复计算，将嵌套循环问题优化为线性扫描。它在字符串处理、子数组求和、区间统计等场景中表现卓越，是面试与工程实践中的高频考点。本文将用Java从零构建滑动窗口框架，深入讲解其固定窗口与可变窗口两种模式，并结合经典题目展示如何与哈希表协同工作。
一、为什么需要滑动窗口
在解决子数组或子串问题时，暴力解法通常需要双重循环枚举所有可能的区间，时间复杂度为 O(n²)。例如：
- 寻找字符串中无重复字符的最长子串
- 找到覆盖目标子串所有字符的最小窗口
- 统计满足条件的固定长度子数组个数
滑动窗口的核心洞察在于：当窗口从左侧收缩或向右侧扩展时，区间内的很多信息可以复用，无需重新计算。通过维护左右两个指针，窗口在数组或字符串上”滑动”，将时间复杂度降为 O(n)。
二、滑动窗口的两种模式
2.1 固定窗口大小
窗口长度保持不变，右指针扩展时左指针同步跟进。适用于：固定长度的子数组最大值/平均值、长度为 k 的子串统计等。
2.2 可变窗口大小
窗口大小动态变化，通常右指针负责扩展，左指针在条件不满足时收缩。适用于：最小覆盖子串、最长无重复子串等。
三、可变窗口框架实现
以下是滑动窗口可变模式的通用Java框架，包含详细注释：
import java.util.HashMap;
import java.util.Map;
/**
* 滑动窗口算法框架（可变窗口）
* 适用于：最小覆盖子串、最长无重复子串、找到所有字母异位词等
*/
public class SlidingWindow {
/**
* 滑动窗口通用框架
* @param s 主字符串
* @param t 目标模式（可选，根据题目需求）
* @return 满足条件的结果
*/
public String minWindow(String s, String t) {
// 1. 用哈希表记录目标字符的需求
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
// 2. 窗口内字符计数
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0; // 左右指针
int valid = 0; // 满足need条件的字符种类数
int start = 0, minLen = Integer.MAX_VALUE; // 记录最小窗口位置
// 3. 右指针扩展窗口
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++; // 某个字符恰好满足需求
}
}
// 4. 左指针收缩窗口（当条件满足时）
while (valid == need.size()) {
// 更新最小窗口
if (right - left < minLen) {
start = left;
minLen = 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 minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
四、经典题目实战
4.1 最长无重复字符子串
给定字符串，找出不含有重复字符的最长子串长度。
/**
* 最长无重复字符子串
* 思路：右指针扩展，遇到重复字符则收缩左边界至重复字符之后
* 时间复杂度：O(n)，每个字符最多被访问两次
*/
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> charIndex = new HashMap<>(); // 记录字符最新位置
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符已存在且位于窗口内，收缩左边界
if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
left = charIndex.get(c) + 1;
}
// 更新字符最新位置
charIndex.put(c, right);
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
4.2 找到字符串中所有字母异位词
给定字符串 s 和 p，找到 s 中所有 p 的异位词（排列）的起始索引。
/**
* 找到字符串中所有字母异位词
* 思路：固定窗口大小为p.length()，用数组计数比较
* 时间复杂度：O(n)，空间复杂度：O(1)（固定大小数组）
*/
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) return result;
int[] pCount = new int[26]; // p的字符计数
int[] windowCount = new int[26]; // 窗口内字符计数
for (char c : p.toCharArray()) {
pCount[c - 'a']++;
}
// 初始化窗口
for (int i = 0; i < p.length(); i++) {
windowCount[s.charAt(i) - 'a']++;
}
if (Arrays.equals(pCount, windowCount)) {
result.add(0);
}
// 滑动窗口：右进左出
for (int right = p.length(); right < s.length(); right++) {
windowCount[s.charAt(right) - 'a']++; // 右侧字符进入
windowCount[s.charAt(right - p.length()) - 'a']--; // 左侧字符移出
if (Arrays.equals(pCount, windowCount)) {
result.add(right - p.length() + 1);
}
}
return result;
}
4.3 固定窗口：子数组最大平均数
给定数组 nums 和整数 k，找出长度为 k 的子数组的最大平均数。
/**
* 子数组最大平均数 I
* 思路：先计算第一个窗口的和，然后滑动更新
* 时间复杂度：O(n)，空间复杂度：O(1)
*/
public double findMaxAverage(int[] nums, int k) {
double windowSum = 0;
// 初始化第一个窗口
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
double maxSum = windowSum;
// 窗口滑动：右进左出
for (int right = k; right < nums.length; right++) {
windowSum += nums[right]; // 右侧元素进入
windowSum -= nums[right - k]; // 左侧元素移出
maxSum = Math.max(maxSum, windowSum);
}
return maxSum / k;
}
五、滑动窗口的适用场景总结
| 问题类型 | 判断特征 | 窗口类型 |
|---|---|---|
| 最长/最短子串满足条件 | 字符串中连续区间 | 可变窗口 |
| 固定长度子数组统计 | 长度为k的连续区间 | 固定窗口 |
| 排列/异位词检测 | 字符频率相同即可 | 固定窗口 |
| 子数组和/积约束 | 和/积大于或小于阈值 | 可变窗口 |
| 至多K个不同字符 | 允许有限种类字符 | 可变窗口 |
六、复杂度对比
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 数据量极小 |
| 滑动窗口 | O(n) | O(k)或O(1) | 连续子数组/子串问题 |
| 前缀和 | O(n)预处理，O(1)查询 | O(n) | 多次任意区间查询 |
滑动窗口的优势在于单次线性扫描即可完成，无需额外预处理，特别适合数据流或只需遍历一次的场景。
七、完整测试程序
import java.util.*;
public class SlidingWindowDemo {
static class SlidingWindow {
// 最小覆盖子串
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0, valid = 0;
int start = 0, minLen = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(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 < minLen) {
start = left;
minLen = right - left;
}
char d = s.charAt(left++);
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) valid--;
window.put(d, window.get(d) - 1);
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
// 最长无重复子串
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> charIndex = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
left = charIndex.get(c) + 1;
}
charIndex.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// 字母异位词
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) return result;
int[] pCount = new int[26];
int[] windowCount = new int[26];
for (char c : p.toCharArray()) pCount[c - 'a']++;
for (int i = 0; i < p.length(); i++) windowCount[s.charAt(i) - 'a']++;
if (Arrays.equals(pCount, windowCount)) result.add(0);
for (int right = p.length(); right < s.length(); right++) {
windowCount[s.charAt(right) - 'a']++;
windowCount[s.charAt(right - p.length()) - 'a']--;
if (Arrays.equals(pCount, windowCount)) result.add(right - p.length() + 1);
}
return result;
}
// 最大平均数
public double findMaxAverage(int[] nums, int k) {
double windowSum = 0;
for (int i = 0; i < k; i++) windowSum += nums[i];
double maxSum = windowSum;
for (int right = k; right < nums.length; right++) {
windowSum += nums[right] - nums[right - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum / k;
}
}
public static void main(String[] args) {
SlidingWindow sw = new SlidingWindow();
// 测试1：最小覆盖子串
System.out.println("=== 最小覆盖子串 ===");
String s1 = "ADOBECODEBANC", t1 = "ABC";
System.out.println("输入: s=" + s1 + ", t=" + t1);
System.out.println("输出: " + sw.minWindow(s1, t1)); // BANC
System.out.println();
// 测试2：最长无重复子串
System.out.println("=== 最长无重复子串 ===");
String s2 = "abcabcbb";
System.out.println("输入: " + s2);
System.out.println("输出: " + sw.lengthOfLongestSubstring(s2)); // 3
System.out.println();
// 测试3：字母异位词
System.out.println("=== 找到所有字母异位词 ===");
String s3 = "cbaebabacd", p3 = "abc";
System.out.println("输入: s=" + s3 + ", p=" + p3);
System.out.println("输出: " + sw.findAnagrams(s3, p3)); // [0, 6]
System.out.println();
// 测试4：最大平均数
System.out.println("=== 子数组最大平均数 ===");
int[] nums = {1, 12, -5, -6, 50, 3};
int k = 4;
System.out.println("输入: " + Arrays.toString(nums) + ", k=" + k);
System.out.println("输出: " + sw.findMaxAverage(nums, k)); // 12.75
}
}
八、总结
滑动窗口的精髓在于用双指针维护一个动态区间，避免重复计算。掌握这一技巧的关键是理解三个问题：右指针何时扩展（遍历数据时）、左指针何时收缩（条件被满足或违反时）、窗口状态如何更新（进入和移出时的增量维护）。
与哈希表结合后，滑动窗口可以高效处理字符频率统计、元素存在性判断等问题，成为解决子串和子数组问题的利器。建议在理解框架的基础上，多练习 LeetCode 第 3、76、209、438、567、239 题，巩固对不同场景的适应能力。
