滑动窗口

1 无重复字符的最长子串

【原始题目】

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

示例 1： 输入：s = "abcabcbb" 输出：3 解释：无重复字符的最长子串是 "abc"，长度为 3。"bca"、"cab" 等也是正确答案。

示例 2： 输入：s = "bbbbb" 输出：1 解释：最长子串是 "b"，长度为 1。

示例 3： 输入：s = "pwwkew" 输出：3 解释：最长子串是 "wke"，长度为 3。注意 "pwke" 是子序列，不是子串。

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

【题目速记】

在字符串中找最长连续子串，要求子串内所有字符都不重复。字符集包含字母、数字、符号和空格，长度最大五万，区分“子串”（连续）和“子序列”（不连续）。

【题解】

一句话速通：使用滑动窗口维护一个无重复字符的区间，右指针不断向右扩展，遇到重复字符时，通过哈希集合判断并将左指针逐步右移，直到窗口内再次无重复，全程记录最大窗口长度。

【算法思想】

• 滑动窗口：用左右指针界定当前无重复子串，右指针主动扩展，左指针被动收缩。
• 哈希集合：存放当前窗口内的字符，用于 $ O(1) $ 判断新字符是否重复。

【核心思路】

1. 初始化左指针 left = 0，最大长度 max = 0，哈希集合 set 记录窗口内字符。
2. 右指针 right 从 0 到 n-1 遍历字符串。
3. 若 s[right] 已在 set 中，说明重复，循环从 set 中移除 s[left] 并将 left 右移，直到没有重复。
4. 将 s[right] 加入 set，更新 max = Math.max(max, right - left + 1)。
5. 返回 max。

【复杂度】

• 时间复杂度 $ O(n) $ ：左右指针各遍历字符串一次，每个字符最多被访问两次。
• 空间复杂度 $ O(min(m, n)) $ ： $ m $ 为字符集大小，实际取决于窗口内不同字符数，最多为字符集上限（如 ASCII 128），可视为 $ O(1) $ 或 $ O(n) $。

【伪代码】

set = 空集合
left = 0, max = 0
for right 从 0 到 s长度-1:
    while set 包含 s[right]:
        set 移除 s[left]
        left++
    set 添加 s[right]
    max = max(max, right - left + 1)
返回 max

【易错点】

• 遇到重复时是用 while 而不是 if，因为可能需要连续移除多个字符。
• 移除的是 s[left] 而不是直接移除 s[right]，先移左端再右移指针。
• 空字符串返回 0，循环不执行直接返回初始 max，代码本身能正确处理。

【完整代码】

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, max = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            while (set.contains(c)) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(c);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}

【题解】

一句话速通：在滑动窗口中用哈希表记录每个字符最近一次出现的下标，当右指针遇到重复字符时，左指针直接跳跃到重复字符上一次出现位置的下一位，省去一步步收缩的过程，一次遍历获得最大长度。

【算法思想】

• 滑动窗口：同样维护无重复子串的左右边界。
• 哈希表：存储“字符→最新下标”的映射，遇到重复时提供左指针应该跳到的目标位置。

【核心思路】

1. 初始化左指针 left = 0，最大长度 max = 0，哈希表 map 记录字符最近出现位置。
2. 右指针 right 从 0 到 n-1 遍历字符串，当前字符 c = s[right]。
3. 若 c 已存在于 map 中，则 left 尝试跳到 map.get(c) + 1 的位置，但需与当前 left 取较大值，防止左指针回退。
4. 更新 map 中 c 的值为 right。
5. 更新 max = Math.max(max, right - left + 1)。
6. 返回 max。

【复杂度】

• 时间复杂度 $ O(n) $ ：左右指针各遍历一次，哈希表操作为 $ O(1) $。
• 空间复杂度 $ O(min(m, n)) $ ：哈希表存储字符及其下标，字符集大小 $ m $，通常远小于 $ n $，可认为是 $ O(1) $。

【伪代码】

map = 空哈希表  // 字符 -> 最新下标
left = 0, max = 0
for right 从 0 到 s长度-1:
    c = s[right]
    如果 map 包含 c:
        left = max(left, map.get(c) + 1)
    map 放入 (c, right)
    max = max(max, right - left + 1)
返回 max

【易错点】

• 左指针跳跃时必须 left = Math.max(left, map.get(c) + 1)，不能直接赋值，否则可能导致 left 回退到之前已经排除的位置。
• 无论是否重复，都要更新 map 中字符的最新下标，否则后续判断会基于过时的位置。
• 同样要考虑空字符串和空格等字符的边界情况。

【完整代码】

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, max = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, right);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}

2 找到字符串中所有字母异位词

【原始题目】

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

示例 1：
输入：s = "cbaebabacd", p = "abc"
输出：[0,6]

示例 2：
输入：s = "abab", p = "ab"
输出：[0,1,2]

提示： 字符串长度不超过 $ 3 \times 10^4 $ ，且仅包含小写字母。

【题目速记】

在长串 s 中找所有 p 的排列子串。等价于：找出 s 中所有长度与 p 相同、且每种字母出现次数与 p 完全一致的子串，返回它们的起始下标。小写字母，长度最多 3 万。

【题解】

一句话速通：固定窗口横扫 + 数组计数，窗口右移时“减左加右”更新频率，每次与 p 的频率数组比较，相等就记录左端点。

【算法思想】

• 滑动窗口（固定长度）：维护一个长度为 len(p) 的窗口在 s 上滑动，每个位置统计窗口内字符频率。
• 数组 / 哈希表：用两个大小为 26 的整型数组 need 和 window 分别记录 p 的字符频率和当前窗口的频率，方便快速比较。

【核心思路】

1. 预处理 need[26] 数组，统计 p 中各字符出现次数。
2. 初始化窗口：将 s 的前 len(p) 个字符填入 window[26]。
3. 如果 Arrays.equals(need, window)，记录起始索引 0。
4. 窗口右移，i 从 len(p) 到 len(s)-1：
   • 窗口左端字符移出：下标 i - pLen，在 window 中减去对应计数。
   • 窗口右端字符移入：下标 i，在 window 中加上对应计数。
   • 检查 Arrays.equals(need, window)，相等则记录起始索引 i - pLen + 1。
5. 返回结果列表。

【复杂度】

• 时间复杂度 $ O(n \cdot 26) \rightarrow O(n) $ ：n 是 s 的长度，每次移动窗口需要比较两个长度为 26 的数组，常数时间。
• 空间复杂度 $ O(1) $ ：两个长度为 26 的计数数组，与输入规模无关。

【伪代码】

function findAnagrams(s, p):
    n = s.length, m = p.length
    if n < m: return empty list
    need = count(p)           // 统计 p 的字符频率
    window = count(s[0..m-1]) // 初始窗口
    res = []
    if need equals window: res.add(0)
    for i from m to n-1:
        left = i - m
        移出 s[left]  -> window 减1
        移入 s[i]     -> window 加1
        if need equals window: res.add(left+1)
    return res

【易错点】

• 忘记处理 s 长度小于 p 长度的情况，直接返回空列表。
• 数组索引错误：移出字符的下标是 i - pLen，新起点是 i - pLen + 1。
• 使用 == 或 equals 比较数组时误用 ==，必须用 Arrays.equals。

【完整代码】

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (n < m) return res;

        int[] need = new int[26];
        int[] window = new int[26];
        for (char c : p.toCharArray()) need[c - 'a']++;
        for (int i = 0; i < m; i++) window[s.charAt(i) - 'a']++;

        if (Arrays.equals(need, window)) res.add(0);

        for (int i = m; i < n; i++) {
            // 移出左端字符
            window[s.charAt(i - m) - 'a']--;
            // 移入右端字符
            window[s.charAt(i) - 'a']++;
            if (Arrays.equals(need, window)) {
                res.add(i - m + 1);
            }
        }
        return res;
    }
}

【题解】

一句话速通：双指针维护一个变长窗口，用 diff 整数记录窗口与 p 的字符种类差异，当窗口长度刚好等于 p 长度且 diff == 0 时收割左指针。

【算法思想】

• 双指针 / 变长滑动窗口：右指针主动扩张，左指针被动收缩，维持窗口长度始终不超过 p 的长度。
• 差异计数：只用一个 need 数组记录 p 的字符频率，窗口内每个字符的“欠账”由 need 的值反映，用一个整型 diff 表示当前窗口中有多少种字符的频率与 p 不同，避免每次比较 26 个位置。

【核心思路】

1. need[26] 统计 p 的字符频率，初始 diff 为 p 中不同字符的种类数。
2. 右指针 r 遍历 s，每次将 s[r] 视为“入窗”：
   • 将 need[s[r]] 减 1，若减到 0 说明该字符数量已满足，diff--。
   • 如果窗口长度超过 m，左指针 l 指向的字符“出窗”：
     • 将 need[s[l]] 加 1，若加完后等于 1，说明原来该字符刚好满足，现在不满足了，diff++。
     • 左指针 l++。
   • 当 r - l + 1 == m 且 diff == 0 时，l 就是一个合法起点，记录下来。
3. 最终返回结果列表。

【复杂度】

• 时间复杂度 $ O(n) $ ：每个字符最多被左右指针各访问一次，无额外 26 次比较。
• 空间复杂度 $ O(1) $ ：一个大小为 26 的数组。

【伪代码】

function findAnagrams(s, p):
    need = count(p)
    diff = need 中非零元素的个数    // 不同字符种类数
    l = 0, res = []
    for r in 0..n-1:
        c = s[r]
        need[c]--
        if need[c] == 0: diff--     // 该字符数量满足
        
        if r - l + 1 > p.length():
            c_left = s[l]
            need[c_left]++
            if need[c_left] == 1: diff++   // 该字符由满足变不满足
            l++
        
        if r - l + 1 == p.length() and diff == 0:
            res.add(l)
    return res

【易错点】

• diff 的更新条件严格依赖 need 的变化：减到 0 才减少 diff，加到 1 才增加 diff，不是任意变化都改 diff。
• 窗口长度控制的时机：通常是先加入右指针字符，再判断是否超长，超长再处理左指针，最后判断是否符合条件。顺序不能乱。
• 当 p 中有重复字符时，need 初始值可能大于 1，因此 diff 记录的是“种类”而非总次数，注意不要混淆。

【完整代码】

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (n < m) return res;

        int[] need = new int[26];
        for (char c : p.toCharArray()) need[c - 'a']++;

        int diff = 0;
        for (int cnt : need) {
            if (cnt > 0) diff++;
        }

        int l = 0;
        for (int r = 0; r < n; r++) {
            // 右边界入窗
            int idxR = s.charAt(r) - 'a';
            need[idxR]--;
            if (need[idxR] == 0) diff--;

            // 窗口超长，左边界出窗
            if (r - l + 1 > m) {
                int idxL = s.charAt(l) - 'a';
                need[idxL]++;
                if (need[idxL] == 1) diff++;
                l++;
            }

            // 判断合法异位词
            if (r - l + 1 == m && diff == 0) {
                res.add(l);
            }
        }
        return res;
    }
}