滑动窗口算法

滑动窗口（Sliding Window）是处理子串/子数组问题的高效算法，通过在数组/字符串上维护一个可变窗口，避免重复计算，将时间复杂度优化到 O(n)。

核心思想

• 维护一个窗口（由 left、right 双指针界定）
• right 指针向右扩展窗口（探索新元素）
• left 指针向右收缩窗口（移除非法元素）
• 窗口内始终保持某种有效状态

经典问题：无重复字符的最长子串

问题描述

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

滑动窗口解法

public int lengthOfLongestSubstring(String s) {
    // 字符 → 最近出现的位置
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        
        // 如果字符已存在，移动左边界到重复位置的下一位
        if (map.containsKey(c)) {
            // 取 max 防止 left 回退
            left = Math.max(left, map.get(c) + 1);
        }
        
        // 更新字符最近位置
        map.put(c, right);
        
        // 计算当前窗口长度，更新最大值
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

复杂度分析

维度	值	说明
时间复杂度	O(n)	每个字符最多被访问两次（进窗口 + 出窗口）
空间复杂度	O(min(m, n))	m 为字符集大小（ASCII 128 / Unicode），n 为字符串长度

变体：数组代替 HashMap

// 当字符集较小时（如 ASCII），可以用数组替代 HashMap 优化性能
public int lengthOfLongestSubstring(String s) {
    int[] lastIndex = new int[128]; // ASCII 字符集
    int maxLen = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        left = Math.max(left, lastIndex[c]);
        lastIndex[c] = right + 1; // +1 表示下一个不重复的位置
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

滑动窗口通用模板

public int slidingWindow(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int ans = 0; // 或其它需要维护的结果
    
    while (right < s.length()) {
        // 1. 扩展窗口：将 s[right] 加入窗口
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        right++;
        
        // 2. 窗口不满足条件时，收缩窗口
        while (/* 窗口需要收缩的条件 */) {
            char d = s.charAt(left);
            window.put(d, window.get(d) - 1);
            if (window.get(d) == 0) {
                window.remove(d);
            }
            left++;
        }
        
        // 3. 更新答案（此时窗口满足条件）
        ans = Math.max(ans, right - left);
    }
    
    return ans;
}

常见滑动窗口题型

类型	题目	关键条件
最小覆盖子串	LeetCode 76	窗口包含所有目标字符
无重复最长子串	LeetCode 3	窗口内无重复字符
字符串排列	LeetCode 567	窗口内字符计数与目标串相同
找到所有字母异位词	LeetCode 438	窗口内字符计数与目标串相同
滑动窗口最大值	LeetCode 239	使用双端队列（Deque）

参考链接

• 快手电商-一面-19题总结 — Q18 无重复字符的最长子串
• Java-Map-computeIfAbsent — HashMap API