Leetcode Hot100 滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 创建一个哈希集合，用于记录当前窗口中的字符
        Set<Character> occ = new HashSet<Character>();
        int n = s.length(); // 定义字符串长度，后续要多次使用

        // rk 是右指针，初始值为 -1，表示还没有开始移动
        // ans 用于记录最长无重复子串的长度
        int rk = -1, ans = 0;

        // 确定滑动窗口的范围，i 到 rk 个字符是一个极长的无重复字符子串

        // i 是左指针，从字符串的开头开始遍历
        for (int i = 0; i < n; ++i) {
            // 如果不是初次遍历（i != 0），需要移除左指针前一个字符
            if (i != 0) {
                occ.remove(s.charAt(i - 1));  // 这样可以保证当前窗口中不包含重复字符
            }

            // 移动右指针，直到遇到重复字符或到达字符串末尾
            // rk + 1 < n：确保右指针不越界
            // !occ.contains(s.charAt(rk + 1))：确保下一个字符不在当前窗口中
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 将下一个字符添加到集合中
                occ.add(s.charAt(rk + 1));
                // 右指针向右移动
                ++rk;
            }

            // 如果不满足条件就执行下面的更新操作

            // 更新最长无重复子串的长度
            // rk - i + 1 是当前窗口的长度
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

**复杂度分析：**
- **时间复杂度：O(n)**，其中 n 是字符串的长度。左指针和右指针都最多遍历字符串一次，因此总时间复杂度是 O(n)。
- **空间复杂度：O(min(m, n))**，其中 m 是字符集的大小（例如 ASCII 字符集大小为 128），n 是字符串的长度。哈希集合最多存储 min(m, n) 个字符。

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>();
        // 创建一个计数数组，用于记录字符出现的次数差
        int[] count = new int[26];

        // 初始化计数数组：
        // 用一个数组来存储 给定长度内窗口中 不同字符出现的次数
        // 如果滑动窗口出现 p 中的字符，计数减1，否则加1
        // 目的就是让这个缓存数组中的 次数记录为 0 才说明是无差异
        for (int i = 0; i < pLen; ++i) {
            // 通过charAt方法获取当前字符的索引进行计数，即可得到本字符在count数组中的位置再进行增减
            ++count[s.charAt(i) - 'a'];// 窗口内字符出现一次加1
            --count[p.charAt(i) - 'a'];// p中字符出现一次减1
        }


        // 计算 differ 变量，表示 count 数组中非零元素的数量

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }
        // differ 为 0 时，表示当前窗口是 p 的异位词


        // 检查初始窗口是否是异位词
        if (differ == 0) {
            ans.add(0);
        }



        // 以下就是通过滑动窗口判断原句中是否存在其他的异位词

        // 滑动窗口：从 i=0 开始，每次移动窗口一位
        for (int i = 0; i < sLen - pLen; ++i) {

            // 处理移出窗口的字符（s.charAt(i)）
            if (count[s.charAt(i) - 'a'] == 1) {
                // 窗口中字母 s[i] 的数量与 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {
                // 窗口中字母 s[i] 的数量与 p 中的数量从相同变得不同
                ++differ;
            }

            // 因为字符离开了滑动窗口，那么就移除掉这个字符的计数
            --count[s.charAt(i) - 'a'];

            // 处理移入窗口的字符（s.charAt(i+pLen)）
            if (count[s.charAt(i + pLen) - 'a'] == -1) {
                // 窗口中字母 s[i+pLen] 的数量与 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {
                // 窗口中字母 s[i+pLen] 的数量与 p 中的数量从相同变得不同
                ++differ;
            }

            // 增加移入字符的计数
            ++count[s.charAt(i + pLen) - 'a'];

            // 如果 differ 为 0，说明当前窗口是 p 的异位词
            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

**复杂度分析：**
- **时间复杂度：O(n)**，其中 n 是字符串 s 的长度。初始化计数数组需要 O(pLen) 时间，计算 differ 需要 O(26) 时间，滑动窗口遍历需要 O(sLen - pLen) 时间，总时间复杂度为 O(sLen)。
- **空间复杂度：O(1)**，只使用了固定大小的计数数组（长度为 26），因此空间复杂度是常数级别的。