Java 滑动窗口算法详解与 LeetCode 题解

图解：

数组：[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）
• 满足条件的最长/最短子数组

模板：

public int variableWindow(String s) {
    int left = 0, right = 0;
    int result = 0;
    Map<Character, Integer> window = new HashMap<>();
    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）

import java.util.*;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 1. Java 中必须先判断 null（LeetCode 可能传入 null）
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 2. 初始化窗口边界
        int left = 0, right = 0;
        // 3. 初始化结果和窗口状态
        int maxLen = 0;
        // Java 中 HashSet 用于快速判断字符是否存在（O(1) 时间复杂度）
        Set<Character> window = new HashSet<>();
        // 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 优化）

import java.util.*;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int left = 0, right = 0;
        int maxLen = 0;
        // 用 HashMap 存储字符和它的索引（优化：可以直接跳到重复字符的下一个位置）
        Map<Character, Integer> window = new HashMap<>();
        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）

import java.util.Arrays;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 用数组替代 HashMap（Java 中 ASCII 字符数组比 HashMap 更高效，空间复杂度 O(1)）
        int[] loc = new int[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 字符）

import java.util.*;

public class Solution {
    // Java 处理 Unicode 字符的版本（兼容中文/特殊字符）
    public int lengthOfLongestSubstringUnicode(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int maxLen = 0, start = 0;
        // 必须使用 HashMap，因为 Unicode 字符集太大（65536+）
        Map<Character, Integer> loc = new HashMap<>();
        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 = new HashMap<>();

// 正确写法：在文件开头导入
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

3.3 错误三：未处理 null 输入

// 错误写法：未判断 null
public int lengthOfLongestSubstring(String s) {
    int len = s.length(); // 如果 s 是 null，抛出 NullPointerException
}

// 正确写法：先判断 null
public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
}

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 = new HashMap<>();
// 错误：未判断 null
int count = map.get('a'); // 如果 'a' 不存在，返回 null，自动拆箱时抛 NullPointerException

// 正确：使用 getOrDefault()
int count = map.getOrDefault('a', 0); // 如果不存在，返回默认值 0

四、Java 滑动窗口通用模板

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

import java.util.*;

public class VariableWindowTemplate {
    // Java 不定长滑动窗口通用模板
    public int variableWindow(String s) {
        // 1. 边界判断
        if (s == null || s.length() == 0) return 0;
        // 2. 初始化
        int left = 0, right = 0, result = 0;
        Map<Character, Integer> window = new HashMap<>();
        // 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 定长窗口模板

public class FixedWindowTemplate {
    // Java 定长滑动窗口通用模板
    public int fixedWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return 0;
        }
        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 = new HashMap<>();
map.put('a', 1);

// 方式二：int[] 数组（更快）
int[] count = new int[128]; // ASCII 字符集
count['a'] = 1;

5.3 避免频繁创建对象

// 错误：在循环内创建对象
for (int i = 0; i < n; i++) {
    Map<Character, Integer> map = new HashMap<>();
}

// 正确：在循环外创建对象
Map<Character, Integer> map = new HashMap<>();
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 同类题推荐