Yabin's Tech Journey

Day 12 - 滑动窗口进阶 ​

📅 日期：2026年1月19日
🎯 主题：滑动窗口进阶 + 最长窗口与固定长度窗口

今日题目 ​

题目1：无重复字符的最长子串 (Longest Substring Without Repeating Characters) ​

难度：⭐⭐ 中等

链接：LeetCode 3. 无重复字符的最长子串

题目描述 ​

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

示例：

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

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

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

解题思路 ​

方法一：滑动窗口 + 哈希表 ✅ 推荐

核心思想：

  1. 用哈希表 map 记录每个字符最后出现的位置（索引）
  2. 用 left、right 表示窗口 [left, right]
  3. right 右移，如果 s[right] 在 map 中且位置 >= left，说明窗口内出现重复，将 left 移动到 map.get(s[right]) + 1
  4. 更新 map 中 s[right] 的位置为 right，并用 right - left + 1 更新最大长度
  5. 重复直到 right 扫完字符串

关键点：

  • 用哈希表记录字符最后出现位置，避免重复扫描
  • 只有当重复字符在窗口内（>= left）时才移动 left
  • 时间复杂度 O(n)，空间复杂度 O(min(n, m))，m 为字符集大小

代码实现 ​

java
import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 如果字符已存在且在当前窗口内，移动左边界
            if (map.containsKey(c) && map.get(c) >= left) {
                left = map.get(c) + 1;
            }
            // 更新字符位置
            map.put(c, right);
            // 更新最大长度
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

方法二：滑动窗口 + 字符数组（优化）

如果字符集较小（如只有字母），可以用数组代替哈希表：

java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // ASCII 字符集，128 足够
        int[] lastIndex = new int[128];
        Arrays.fill(lastIndex, -1);
        
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 如果字符已存在且在当前窗口内，移动左边界
            if (lastIndex[c] >= left) {
                left = lastIndex[c] + 1;
            }
            // 更新字符位置
            lastIndex[c] = right;
            // 更新最大长度
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

复杂度分析 ​

  • 时间复杂度：O(n)，每个字符最多访问一次
  • 空间复杂度：O(min(n, m))，m 为字符集大小（哈希表）或 O(m)（数组）

题目2：找到字符串中所有字母异位词 (Find All Anagrams in a String) ​

难度：⭐⭐ 中等

链接：LeetCode 438. 找到字符串中所有字母异位词

题目描述 ​

给定两个字符串 s 和 p，找到 s 中所有 p 的 字母异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

字母异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例：

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

提示：

  • 1 <= s.length, p.length <= 3 * 10^4
  • s 和 p 仅包含小写字母

解题思路 ​

方法一：滑动窗口 + 哈希表（固定长度窗口） ✅ 推荐

核心思想：

  1. 用哈希表 need 统计 p 中每个字符需要的次数，用 window 统计当前窗口中各字符出现次数
  2. 用 valid 表示当前窗口内已满足「需要」的字符种类数
  3. 窗口固定长度为 p.length()，right 右移加入字符，left 同步右移移出字符
  4. 当窗口长度等于 p.length() 且 valid == need.size() 时，说明找到字母异位词，记录 left
  5. 重复直到 right 扫完字符串

关键点：

  • 固定长度窗口：窗口大小始终为 p.length()
  • 用 valid 与 need.size() 比较判断是否匹配
  • 窗口移动时，先移入 right，再移出 left，保持窗口大小不变

代码实现 ​

java
import java.util.*;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }

        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        // 统计 p 中每个字符需要的次数
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int valid = 0;

        for (int right = 0; right < s.length(); right++) {
            // 移入字符
            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++;
                }
            }

            // 窗口大小超过 p.length()，移出字符
            if (right - left + 1 > p.length()) {
                char leftChar = s.charAt(left);
                if (need.containsKey(leftChar)) {
                    if (window.get(leftChar).equals(need.get(leftChar))) {
                        valid--;
                    }
                    window.put(leftChar, window.get(leftChar) - 1);
                }
                left++;
            }

            // 窗口大小等于 p.length() 且 valid 等于 need.size()，找到字母异位词
            if (right - left + 1 == p.length() && valid == need.size()) {
                result.add(left);
            }
        }

        return result;
    }
}

方法二：滑动窗口 + 数组（优化）

如果字符集较小（如只有小写字母），可以用数组代替哈希表：

java
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }

        int[] need = new int[26];
        int[] window = new int[26];

        // 统计 p 中每个字符需要的次数
        for (int i = 0; i < p.length(); i++) {
            need[p.charAt(i) - 'a']++;
        }

        int left = 0;
        int valid = 0;
        int needCount = 0;
        
        // 统计 need 中非零字符的种类数
        for (int count : need) {
            if (count > 0) {
                needCount++;
            }
        }

        for (int right = 0; right < s.length(); right++) {
            // 移入字符
            int c = s.charAt(right) - 'a';
            if (need[c] > 0) {
                window[c]++;
                if (window[c] == need[c]) {
                    valid++;
                }
            }

            // 窗口大小超过 p.length()，移出字符
            if (right - left + 1 > p.length()) {
                int leftChar = s.charAt(left) - 'a';
                if (need[leftChar] > 0) {
                    if (window[leftChar] == need[leftChar]) {
                        valid--;
                    }
                    window[leftChar]--;
                }
                left++;
            }

            // 窗口大小等于 p.length() 且 valid 等于 needCount，找到字母异位词
            if (right - left + 1 == p.length() && valid == needCount) {
                result.add(left);
            }
        }

        return result;
    }
}

复杂度分析 ​

  • 时间复杂度：O(|s| + |p|)
  • 空间复杂度：O(|p|)，哈希表或数组存储字符

今日总结 ​

学到了什么？ ​

  1. 最长无重复子串：用哈希表记录字符最后出现位置，遇到重复时直接跳到重复字符之后
  2. 固定长度窗口：窗口大小固定，右移时同步移出左边界，适用于匹配、排列等场景
  3. 字符数组优化：字符集较小时用数组代替哈希表，减少空间开销
  4. 窗口收缩时机：最长窗口在遇到重复时收缩，固定窗口在超过长度时收缩

关键技巧 ​

技巧适用场景时间复杂度空间复杂度
最长窗口无重复字符、满足条件最长O(n)O(min(n, m))
固定长度窗口字母异位词、排列匹配O(n)O(k)
哈希表记录位置避免重复扫描O(n)O(m)
数组代替哈希表字符集较小（如26个字母）O(n)O(m)

滑动窗口进阶要点 ​

  1. 最长窗口模式：

    • 右边界扩展，遇到重复或不符合条件时收缩左边界
    • 用哈希表记录字符位置，快速定位重复字符
    • 适用于：无重复字符最长子串、满足条件最长子数组

  2. 固定长度窗口模式：

    • 窗口大小固定，右移时同步移出左边界
    • 用 valid 判断窗口是否满足条件
    • 适用于：字母异位词、字符串排列、固定长度匹配

  3. 常见错误：

    • 最长窗口：忘记检查重复字符是否在窗口内（>= left）
    • 固定窗口：窗口大小判断错误，应该在移入后判断
    • 字符数组：忘记初始化或索引计算错误（c - 'a'）

相似题目推荐 ​

明日计划 ​

  • Day 13 栈
  • 练习：栈的基本操作、括号匹配、表达式求值等题目

Released under the MIT License.

Copyright © 2025-present Wang