---

前言

本文记录力扣Hot100里面关于滑动窗口的两道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解

---

`

一、无重复字符的最长子串

1.题目

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

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

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

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

2.代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合：用于记录当前窗口中已经出现过的字符（判断是否重复）
        Set<Character> occ = new HashSet<Character>();
        int n = s.length(); // 字符串长度
        // 右指针 rk：初始值为 -1，代表窗口的右边界还未开始（在字符串最左侧外面）
        int rk = -1, ans = 0; // ans 记录最长子串的长度

        // 左指针 i 从 0 开始，逐步向右移动（枚举窗口的左边界）
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格时，移除窗口中 i-1 位置的字符（因为窗口左边界右移，该字符不再在窗口内）
                occ.remove(s.charAt(i - 1));
            }

            // 右指针不断向右移动，扩展窗口：
            // 条件1：rk+1 < n（右指针不越界）确保下一个字符不越界（在字符串范围内）。
            // 条件2：窗口中不包含下一个字符（s.charAt(rk+1)）确保下一个字符不在当前窗口中（无重复）
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 将下一个字符加入集合（标记为已出现）
                occ.add(s.charAt(rk + 1));
                // 右指针右移一格
                ++rk;
            }

            // 此时窗口 [i...rk] 是当前左边界 i 下的最长无重复子串
            // 更新最长长度（当前窗口长度 = rk - i + 1）
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

3.关键步骤

// 左指针 i 从 0 开始，逐步向右移动（枚举窗口的左边界）
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格时，移除窗口中 i-1 位置的字符（因为窗口左边界右移，该字符不再在窗口内）
                occ.remove(s.charAt(i - 1));
            }

            // 右指针不断向右移动，扩展窗口：
            // 条件1：rk+1 < n（右指针不越界）确保下一个字符不越界（在字符串范围内）。
            // 条件2：窗口中不包含下一个字符（s.charAt(rk+1)）确保下一个字符不在当前窗口中（无重复）
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 将下一个字符加入集合（标记为已出现）
                occ.add(s.charAt(rk + 1));
                // 右指针右移一格
                ++rk;
            }

            // 此时窗口 [i...rk] 是当前左边界 i 下的最长无重复子串
            // 更新最长长度（当前窗口长度 = rk - i + 1）
            ans = Math.max(ans, rk - i + 1);
        }

循环内的逻辑是：右指针从左到右逐个向后移动（全程单向不回退），左指针初始位置固定；当右指针遇到的新字符导致窗口内出现重复时，左指针会向右移动以收缩窗口（直到窗口内无重复字符）；每次右指针移动后，都会计算当前窗口的长度并更新最大长度；整个过程重复至右指针遍历完字符串所有字符（左指针仅在窗口不满足条件时收缩，并非主动 “出界”）。
而窗口实际上就是左指针和右指针之间的闭区间 [i ，rk] （即对应原字符的子串）。

关于为什么是++rk;
逻辑上的顺序不同：++rk 是 “主动将指针移到新位置”，而 rk++ 是 “先保留旧位置，再被动移到新位置”。这种顺序差异在复杂场景（如嵌套判断）中可能导致逻辑混乱，而 ++rk 更直观地体现了 “扩展窗口右边界” 的意图，避免歧义。

4.例子

演示：以 s = “abcabcbb” 为例

1. 初始状态：i=0，rk=-1，occ 为空，ans=0。

• 左指针 i=0（未移动过，无需移除字符）。
• 右指针扩展：rk+1=0（字符 ‘a’ 不在 occ 中）→ 加入 occ，rk=0；继续：rk+1=1（‘b’ 不在 occ 中）→ 加入，rk=1；继续：rk+1=2（‘c’ 不在 occ 中）→ 加入，rk=2；继续：rk+1=3（‘a’ 已在 occ 中）→ 停止扩展。
• 当前窗口 [0,2]（“abc”），长度 3 → ans=3。

2. 左指针 i=1**：

• 移除 i-1=0 位置的字符 ‘a’ → occ 现在包含 {‘b’,‘c’}。
• 右指针扩展：rk+1=3（‘a’ 不在 occ 中）→ 加入，rk=3；继续：rk+1=4（‘b’ 已在 occ 中）→ 停止扩展。
• 当前窗口 [1,3]（“bca”），长度 3 → ans 保持 3。

3. 左指针 i=2**：

• 移除 i-1=1 位置的字符 ‘b’ → occ 现在包含 {‘c’,‘a’}。
• 右指针扩展：rk+1=4（‘b’ 不在 occ 中）→ 加入，rk=4；继续：rk+1=5（‘c’ 已在 occ 中）→ 停止扩展。
• 当前窗口 [2,4]（“cab”），长度 3 → ans 保持 3。

4. 左指针 i=3**：

• 移除 i-1=2 位置的字符 ‘c’ → occ 现在包含 {‘a’,‘b’}。
• 右指针扩展：rk+1=5（‘c’ 不在 occ 中）→ 加入，rk=5；继续：rk+1=6（‘b’ 已在 occ 中）→ 停止扩展。
• 当前窗口 [3,5]（“abc”），长度 3 → ans 保持 3。

5. 后续步骤（i=4 到 i=7）：右指针扩展时会更快遇到重复字符，窗口长度逐渐减小（如 2、1 等），ans 始终保持 3。
   最终返回 3，符合预期结果。

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

1.题目

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

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

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

2.代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        // 边界条件：如果s的长度小于p，不可能有异位词，直接返回空列表
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        // 用两个数组记录字符频率（26个小写字母，索引0对应'a'，1对应'b'...）
        int[] sCount = new int[26];
        int[] pCount = new int[26];

        // 初始化：统计p的字符频率，以及s中第一个窗口（0到pLen-1）的字符频率
        for (int i = 0; i < pLen; ++i) {
            // s中第i个字符的频率+1（s.charAt(i) - 'a' 得到0-25的索引）
            ++sCount[s.charAt(i) - 'a'];
            // p中第i个字符的频率+1
            ++pCount[p.charAt(i) - 'a'];
        }

        // 检查初始窗口是否与p是异位词（频率数组相同）
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0); // 起始索引0符合条件
        }

        // 滑动窗口：从左到右移动窗口，更新频率数组并检查
        // 窗口移动次数 = sLen - pLen（保证窗口不越界）
        for (int i = 0; i < sLen - pLen; ++i) {
            // 移除窗口左侧的字符（左边界右移，该字符不再在窗口内）
            --sCount[s.charAt(i) - 'a'];
            // 加入窗口右侧的新字符（右边界右移，纳入新字符）
            ++sCount[s.charAt(i + pLen) - 'a'];

            // 检查当前窗口（起始索引i+1）是否与p是异位词
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);   // 记录起始索引
            }
        }

        return ans;
    }
}

3.关键理解

本题与第一题不同的地方在于，本题的滑动窗口长度是固定的，就是字符串p的长度

核心：
用索引代表字母，用索引上具体的值代表频率

    for (int i = 0; i < pLen; ++i) {
            // s中第i个字符的频率+1（s.charAt(i) - 'a' 得到0-25的索引）
            ++sCount[s.charAt(i) - 'a'];
            // p中第i个字符的频率+1
            ++pCount[p.charAt(i) - 'a'];
        }

统计目标串 p 中每个字符的出现频率（存入 pCount 数组）；
统计原串 s 中第一个窗口（起始索引 0、长度等于 pLen）的字符频率（存入 sCount 数组）。

       for (int i = 0; i < sLen - pLen; ++i) {
            // 移除窗口左侧的字符（左边界右移，该字符不再在窗口内）
            --sCount[s.charAt(i) - 'a'];
            // 加入窗口右侧的新字符（右边界右移，纳入新字符）
            ++sCount[s.charAt(i + pLen) - 'a'];

            // 检查当前窗口（起始索引i+1）是否与p是异位词
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);   // 记录起始索引
            }
        }

为什么是 i < sLen- pLen:
窗口右边界的计算：因为循环内含有++sCount[s.charAt(i + pLen) - ‘a’];
i + pLen（加入的新字符索引），这个索引必须 < sLen（否则超出 s 的范围）。

我们看具体的例子理解一下。

4.例子

s = "cbaebabacd"（长度10）、p = "abc"（长度3）为例，完整走一遍代码执行流程

第一步：初始化基础变量

sLen = 10，pLen = 3（sLen > pLen）；

• ans = []（空列表，用于存结果）；
• sCount = [0,0,0,...,0]（26个0），pCount = [0,0,0,...,0]（26个0）。

第二步：统计初始频率（循环 i=0~2）

循环i	操作sCount（s的初始窗口：s[0],s[1],s[2] = c,b,a）	操作pCount（p[0],p[1],p[2] = a,b,c）
0	s[0] = c → 索引2 → sCount[2] +=1 → sCount[2]=1	p[0] = a → 索引0 → pCount[0] +=1 → pCount[0]=1
1	s[1] = b → 索引1 → sCount[1] +=1 → sCount[1]=1	p[1] = b → 索引1 → pCount[1] +=1 → pCount[1]=1
2	s[2] = a → 索引0 → sCount[0] +=1 → sCount[0]=1	p[2] = c → 索引2 → pCount[2] +=1 → pCount[2]=1

循环结束后：

• sCount = [1,1,1,0,0,...0]（仅a/b/c各1次，其余0）；
• pCount = [1,1,1,0,0,...0]（仅a/b/c各1次，其余0）。

第三步：判断初始窗口（i=0）

Arrays.equals(sCount, pCount) → 所有索引值相等 → 返回true → ans.add(0) → ans = [0]。

第四步：滑动窗口循环（i=0~6，共7次循环，i < 10-3=7）

循环i=0（处理窗口起始索引1）

• 移除左边界：s[0] = c → 索引2 → sCount[2] -=1 → sCount[2] = 0；
• 加入右边界：s[0+3] = s[3] = e → 索引4 → sCount[4] +=1 → sCount[4] = 1；
• 此时 sCount = [1,1,0,0,1,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals 对比：索引2（0≠1）→ false → 不加入ans。

循环i=1（处理窗口起始索引2）

移除左边界：s[1] = b → 索引1 → sCount[1] -=1 → sCount[1] = 0；

• 加入右边界：s[1+3] = s[4] = b → 索引1 → sCount[1] +=1 → sCount[1] = 1；
• 此时 sCount = [1,1,0,0,1,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals 对比：索引2（0≠1）→ false → 不加入ans。

循环i=2（处理窗口起始索引3）

移除左边界：s[2] = a → 索引0 → sCount[0] -=1 → sCount[0] = 0；

• 加入右边界：s[2+3] = s[5] = a → 索引0 → sCount[0] +=1 → sCount[0] = 1；
• 此时 sCount = [1,1,0,0,1,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals 对比：索引2（0≠1）→ false → 不加入ans。

循环i=3（处理窗口起始索引4）

移除左边界：s[3] = e → 索引4 → sCount[4] -=1 → sCount[4] = 0；

• 加入右边界：s[3+3] = s[6] = b → 索引1 → sCount[1] +=1 → sCount[1] = 2；
• 此时 sCount = [1,2,0,0,0,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals 对比：索引1（2≠1）、索引2（0≠1）→ false → 不加入ans。

循环i=4（处理窗口起始索引5）

移除左边界：s[4] = b → 索引1 → sCount[1] -=1 → sCount[1] = 1；

• 加入右边界：s[4+3] = s[7] = a → 索引0 → sCount[0] +=1 → sCount[0] = 2；
• 此时 sCount = [2,1,0,0,0,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals 对比：索引0（2≠1）、索引2（0≠1）→ false → 不加入ans。

循环i=5（处理窗口起始索引6）

移除左边界：s[5] = a → 索引0 → sCount[0] -=1 → sCount[0] = 1；

• 加入右边界：s[5+3] = s[8] = c → 索引2 → sCount[2] +=1 → sCount[2] = 1；
• 此时 sCount = [1,1,1,0,0,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals 对比**：所有索引值相等 → true → ans.add(6) → ans = [0,6]。

循环i=6（处理窗口起始索引7）

移除左边界：s[6] = b → 索引1 → sCount[1] -=1 → sCount[1] = 0；

• 加入右边界：s[6+3] = s[9] = d → 索引3 → sCount[3] +=1 → sCount[3] = 1；
• 此时 sCount = [1,0,1,1,0,...0]，pCount = [1,1,1,0,0,...0]；
• Arrays.equals 对比：索引1（0≠1）、索引3（1≠0）→ false → 不加入ans。

第五步：返回结果

最终 ans = [0,6]，即s中起始索引0（子串"cba"）和6（子串"bac"）是p的异位词。

核心总结

1. 本题中滑动窗口的核心是「移除左边界+加入右边界」，保证窗口长度固定为3O（字符串p的长度）；
2. Arrays.equals 逐索引对比频率数组，只有全相等才判定为异位词；

---