Java 滑动窗口 - 附LeetCode经典题解

Java 滑动窗口 - 附LeetCode经典题解

一、什么是滑动窗口？

1.1 形象理解

想象你站在一扇窗户前看风景，窗户可以左右移动，也可以变大变小。你通过这扇窗户观察外面的景色，这就是"滑动窗口"。

在算法中，滑动窗口就是：

• 窗口：数组或字符串中的一段连续子序列
• 滑动：窗口的左右边界可以移动
• 目的：在移动过程中找到满足条件的最优解

1.2 滑动窗口的本质

滑动窗口其实就是双指针的一种应用：

• 左指针（left）：窗口的左边界
• 右指针（right）：窗口的右边界
• 窗口内容：[left, right) 之间的元素（左闭右开区间）

字符串：a b c a b c b b ↑ ↑ left right 窗口内容：[a, b, c]（不包含 right 指向的元素） 

Java 特别注意： 在 Java 中，字符串索引从 0 开始，s.charAt(i) 获取索引 i 的字符。

1.3 滑动窗口的核心思想

核心： 通过移动左右指针，动态调整窗口大小，在 O(n) 时间内找到最优解。

关键点：

1. 右指针不断向右扩大窗口
2. 当窗口不满足条件时，左指针向右收缩窗口
3. 在移动过程中记录最优解

1.4 定长窗口 vs 不定长窗口（重点！）

滑动窗口分为两大类：

1.4.1 定长窗口（固定大小）

特点： 窗口大小固定为 k，只需要滑动，不需要收缩。

适用场景：

• 大小为 k 的子数组最大和
• 长度为 k 的子串问题
• 固定窗口内的统计问题

模板：

publicintfixedWindow(int[] nums,int k){int result =0;int sum =0;for(int right =0; right < nums.length; right++){// 1. 扩大窗口：加入右边界元素 sum += nums[right];// 2. 当窗口大小达到 k 时if(right >= k -1){// 更新结果 result =Math.max(result, sum);// 缩小窗口：移除左边界元素 sum -= nums[right - k +1];}}return result;}

图解：

数组：[1, 3, -1, -3, 5, 3, 6, 7]，k = 3 步骤1：窗口 [1, 3, -1]，sum = 3 步骤2：窗口 [3, -1, -3]，sum = -1 步骤3：窗口 [-1, -3, 5]，sum = 1 步骤4：窗口 [-3, 5, 3]，sum = 5 ... 窗口大小始终为 3，只需要滑动 

1.4.2 不定长窗口（可变大小）

特点： 窗口大小动态变化，需要根据条件收缩窗口。

适用场景：

• 最长无重复字符子串（LeetCode 3）
• 最小覆盖子串（LeetCode 76）
• 满足条件的最长/最短子数组

模板：

publicintvariableWindow(String s){int left =0, right =0;int result =0;Map<Character,Integer> window =newHashMap<>();while(right < s.length()){// 1. 扩大窗口：加入右边界元素char c = s.charAt(right); right++; window.put(c, window.getOrDefault(c,0)+1);// 2. 收缩窗口：当窗口不满足条件时while(窗口不满足条件){char d = s.charAt(left); left++; window.put(d, window.get(d)-1);}// 3. 更新结果 result =Math.max(result, right - left);}return result;}

图解：

字符串：a b c a b c b b 步骤1：窗口 [a]，无重复，长度 = 1 步骤2：窗口 [a, b]，无重复，长度 = 2 步骤3：窗口 [a, b, c]，无重复，长度 = 3 步骤4：窗口 [a, b, c, a]，有重复！收缩窗口 步骤5：窗口 [b, c, a]，无重复，长度 = 3 ... 窗口大小动态变化，需要收缩 

1.4.3 对比总结

记忆技巧：

• 定长窗口：窗口大小固定，像火车车厢，只能整体移动
• 不定长窗口：窗口大小可变，像橡皮筋，可以伸缩

二、LeetCode 第 3 题：无重复字符的最长子串（不定长窗口）

2.1 题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

Java 特殊输入场景：

输入: s = "\t\n\r" // 包含制表符、换行符、回车符 输出: 3 输入: s = "你好世界" // 包含中文（Unicode 字符） 输出: 4 

2.2 解题思路

这是一道典型的不定长滑动窗口问题。

核心思想：

1. 用一个 HashSet 存储窗口内的字符
2. 右指针不断向右扩大窗口，将字符加入 Set
3. 如果遇到重复字符，左指针向右收缩窗口，直到没有重复
4. 在移动过程中记录最大窗口长度

为什么是不定长窗口？

• 窗口大小不固定，需要根据是否有重复字符动态调整
• 当有重复时，左指针收缩窗口；无重复时，右指针扩大窗口

2.3 完整代码（方法一：HashSet）

importjava.util.*;publicclassSolution{publicintlengthOfLongestSubstring(String s){// 1. Java 中必须先判断 null（LeetCode 可能传入 null）if(s ==null|| s.length()==0){return0;}// 2. 初始化窗口边界int left =0, right =0;// 3. 初始化结果和窗口状态int maxLen =0;// Java 中 HashSet 用于快速判断字符是否存在（O(1)时间复杂度）Set<Character> window =newHashSet<>();// 4. 右指针不断向右扩大窗口（不定长窗口的特点）while(right < s.length()){// 4.1 获取右边界的字符char c = s.charAt(right);// 4.2 如果窗口内有重复字符，收缩窗口（不定长窗口的核心）while(window.contains(c)){// 移除左边界的字符 window.remove(s.charAt(left)); left++;// 左指针右移}// 4.3 将右边界字符加入窗口 window.add(c); right++;// 右指针右移// 4.4 更新最大长度 maxLen =Math.max(maxLen, right - left);}return maxLen;}}

时间复杂度： O(n)，每个字符最多被访问两次（一次加入，一次移除）
空间复杂度： O(min(n, m))，m 是字符集大小

2.4 完整代码（方法二：HashMap 优化）

importjava.util.*;publicclassSolution{publicintlengthOfLongestSubstring(String s){if(s ==null|| s.length()==0){return0;}int left =0, right =0;int maxLen =0;// 用 HashMap 存储字符和它的索引（优化：可以直接跳到重复字符的下一个位置）Map<Character,Integer> window =newHashMap<>();while(right < s.length()){char c = s.charAt(right);// 如果字符已存在，且在窗口内if(window.containsKey(c)&& window.get(c)>= left){// 直接跳到重复字符的下一个位置（优化点！） left = window.get(c)+1;}// 更新字符的索引 window.put(c, right);// 更新最大长度 maxLen =Math.max(maxLen, right - left +1); right++;}return maxLen;}}

优化点： 用 HashMap 存储字符的索引，当遇到重复字符时，可以直接跳到重复字符的下一个位置，不需要一个一个移动左指针。

2.5 完整代码（方法三：数组优化 - 仅适用于 ASCII）

importjava.util.Arrays;publicclassSolution{publicintlengthOfLongestSubstring(String s){if(s ==null|| s.length()==0){return0;}// 用数组替代 HashMap（Java 中 ASCII 字符数组比 HashMap 更高效，空间复杂度 O(1)）int[] loc =newint[128];// ASCII 字符集大小为 128// Java 中数组默认值为 0，必须初始化为 -1 避免和索引 0 混淆Arrays.fill(loc,-1);int maxLen =0, start =0;for(int end =0; end < s.length(); end++){char c = s.charAt(end);// 如果字符已存在，且在窗口内if(loc[c]>= start){ start = loc[c]+1;} loc[c]= end; maxLen =Math.max(maxLen, end - start +1);}return maxLen;}}

适用场景： 只包含 ASCII 字符（如英文字母、数字、标点符号）
不适用场景： 包含中文、Emoji 等 Unicode 字符

2.6 完整代码（方法四：处理 Unicode 字符）

importjava.util.*;publicclassSolution{// Java 处理 Unicode 字符的版本（兼容中文/特殊字符）publicintlengthOfLongestSubstringUnicode(String s){if(s ==null|| s.length()==0){return0;}int maxLen =0, start =0;// 必须使用 HashMap，因为 Unicode 字符集太大（65536+）Map<Character,Integer> loc =newHashMap<>();for(int end =0; end < s.length(); end++){char c = s.charAt(end);if(loc.containsKey(c)&& loc.get(c)>= start){ start = loc.get(c)+1;} loc.put(c, end); maxLen =Math.max(maxLen, end - start +1);}return maxLen;}}

2.7 复杂度对比

三、Java 易错点总结（重点！）

3.1 错误一：数组越界

// 错误写法char[] str = s.toCharArray();for(int i =0; i <= str.length; i++){// 注意：应该是 < 而不是 <=char c = str[i];// 当 i = str.length 时，数组越界！}// 正确写法char[] str = s.toCharArray();for(int i =0; i < str.length; i++){// Java 数组下标从 0 开始，到 length-1 结束char c = str[i];}

3.2 错误二：忘记导入包

// 编译错误：找不到 Arrays 类Arrays.fill(loc,-1);// 编译错误：找不到 HashMap 类Map<Character,Integer> map =newHashMap<>();// 正确写法：在文件开头导入importjava.util.Arrays;importjava.util.HashMap;importjava.util.Map;

3.3 错误三：未处理 null 输入

// 错误写法：未判断 nullpublicintlengthOfLongestSubstring(String s){int len = s.length();// 如果 s 是 null，抛出 NullPointerException}// 正确写法：先判断 nullpublicintlengthOfLongestSubstring(String s){if(s ==null|| s.length()==0){return0;}}

3.4 错误四：混淆 charAt() 和 toCharArray()

// 方式一：charAt()（推荐）for(int i =0; i < s.length(); i++){char c = s.charAt(i);// 时间复杂度 O(1)}// 方式二：toCharArray()char[] chars = s.toCharArray();// 创建新数组，时间复杂度 O(n)for(int i =0; i < chars.length; i++){char c = chars[i];}// 错误：频繁调用 toCharArray()for(int i =0; i < s.length(); i++){char[] arr = s.toCharArray();// 每次循环都创建新数组，浪费内存！char c = arr[i];}

3.5 错误五：HashMap 的 get() 返回 null

Map<Character,Integer> map =newHashMap<>();// 错误：未判断 nullint count = map.get('a');// 如果 'a' 不存在，返回 null，自动拆箱时抛 NullPointerException// 正确：使用 getOrDefault()int count = map.getOrDefault('a',0);// 如果不存在，返回默认值 0

四、Java 滑动窗口通用模板

4.1 不定长窗口模板（最常用）

importjava.util.*;publicclassVariableWindowTemplate{// Java 不定长滑动窗口通用模板publicintvariableWindow(String s){// 1. 边界判断if(s ==null|| s.length()==0)return0;// 2. 初始化int left =0, right =0, result =0;Map<Character,Integer> window =newHashMap<>();// 3. 右指针不断向右扩大窗口while(right < s.length()){// 扩大窗口char c = s.charAt(right++); window.put(c, window.getOrDefault(c,0)+1);// 收缩窗口（根据题目条件调整）while(/* 窗口不满足条件 */){char d = s.charAt(left++); window.put(d, window.get(d)-1);if(window.get(d)==0){ window.remove(d);}}// 更新结果 result =Math.max(result, right - left);}return result;}}

4.2 定长窗口模板

publicclassFixedWindowTemplate{// Java 定长滑动窗口通用模板publicintfixedWindow(int[] nums,int k){if(nums ==null|| nums.length ==0|| k <=0){return0;}int result =0;int sum =0;for(int right =0; right < nums.length; right++){// 扩大窗口 sum += nums[right];// 当窗口大小达到 k 时if(right >= k -1){// 更新结果 result =Math.max(result, sum);// 缩小窗口 sum -= nums[right - k +1];}}return result;}}

五、Java 刷题优化技巧

5.1 优先使用 char[] 而非 charAt()

// 方式一：charAt()（简单但稍慢）for(int i =0; i < s.length(); i++){char c = s.charAt(i);// 每次调用方法}// 方式二：toCharArray()（更快）char[] chars = s.toCharArray();// 只创建一次数组for(int i =0; i < chars.length; i++){char c = chars[i];// 直接访问数组}

5.2 用 int[] 替代 HashMap（ASCII 场景）

// 方式一：HashMap（通用但稍慢）Map<Character,Integer> map =newHashMap<>(); map.put('a',1);// 方式二：int[] 数组（更快）int[] count =newint[128];// ASCII 字符集 count['a']=1;

5.3 避免频繁创建对象

// 错误：在循环内创建对象for(int i =0; i < n; i++){Map<Character,Integer> map =newHashMap<>();}// 正确：在循环外创建对象Map<Character,Integer> map =newHashMap<>();for(int i =0; i < n; i++){ map.clear();}

六、总结

6.1 核心要点

1. 滑动窗口 = 双指针 + 动态调整窗口大小
2. 定长窗口：窗口大小固定，只需滑动
3. 不定长窗口：窗口大小可变，需要收缩
4. 右指针扩大窗口，左指针收缩窗口
5. 用 HashSet/HashMap 维护窗口状态
6. 时间复杂度通常是 O(n)

6.2 记忆口诀

定长窗口，固定大小，只需滑动 不定长窗口，动态调整，需要收缩 右指针走，扩大窗口 左指针走，收缩窗口 窗口内，用哈希表 满足条件，更新结果 Java 中，先判 null 

6.3 同类题推荐

希望这篇文章能帮你彻底掌握 Java 滑动窗口算法！记住：定长窗口只需滑动，不定长窗口需要收缩。多刷题，多总结，模板用熟了就能秒杀同类题。加油！

作者：[识君啊]

不要做API的搬运工，要做原理的探索者！