力扣 滑动窗口题目总结

Leetcode3.无重复字符的最长子串

思路：
这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)

力扣官方题解说明：

方法2：滑动窗口法

思路：

我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为上文中的 rk。

在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；

在枚举结束后，我们找到的最长的子串的长度即为答案。

--判断重复字符：

在上面的流程中，我们还需要使用一种数据结构来判断 是否有重复的字符，常用的数据结构为哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。

至此，我们就完美解决了本题。

代码如下：

class Solution {//这道题主要用到思路是：滑动窗口
    // 定义一个方法来计算字符串中无重复字符的最长子串长度
    public int lengthOfLongestSubstring(String s) {
        //定义一个哈希集合，记录每个字符是否出现过（HashSet无序不可重复）
        Set<Character> occ = new HashSet<>(); //Charccter是Char的包装类
        int n = s.length();
        //右指针，初始值为-1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int r = -1,res = 0;
        for(int i = 0; i < n; i ++){
            if(i != 0){
                //左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i-1));
            }
            //不断移动右指针，直到遇到重复字符或者到达字符串末尾
            while(r + 1 < n && !occ.contains(s.charAt(r+1))){
                //没到字符串末尾 && 不包含r+1-->将字符添加到集合中
                occ.add(s.charAt(r+1));
                //右指针右移
                ++r;
            }
            //更新答案，取当前最大无重复子串的长度
            res = Math.max(res, r - i + 1);
        }
        // 返回结果，即最长无重复子串的长度
        return res;
    }
}

这段代码使用了滑动窗口技术，通过移动两个指针（左指针 i 和右指针 r）来寻找最长的无重复字符子串。具体操作如下：

1. 初始化一个字符集合 occ 用于记录当前窗口中包含的字符。
2. 定义右指针 r 的初始值为 -1，表示它还没有开始移动，并定义结果变量res 用于存储最长子串的长度。
3. 通过外层 for 循环移动左指针 i，逐个处理字符串中的字符。
4. 如果左指针 i 不是在初始位置，则移除左指针前一个位置的字符 s.charAt(i - 1)，以确保当前窗口只包含无重复字符。
5. 使用 while 循环不断右移右指针 r，扩展当前窗口，直到遇到重复字符或到达字符串末尾。每次右移时，将当前字符添加到集合 occ 中。
6. 在每次扩展窗口后，更新结果 res 为当前窗口长度（r - i + 1）与之前最大长度中的较大值。
7. 最终返回结果 res，即最长无重复字符子串的长度。

 补充知识点：

在Java中，Character 是一个包装类（wrapper class），它封装了一个基本类型 char 的值。Character 类提供了一些方法来操作字符数据类型。与 char 不同，Character 是一个类，可以用于泛型集合（如 Set、List 等），因为这些集合只能包含对象，而不能包含基本数据类型。

下面是一些关于 Character 类的关键点：

1. 封装基本类型 char：

   • char 是一个基本数据类型，表示单个16位Unicode字符。
   • Character 类将 char 封装为对象，使其能够在需要对象的上下文中使用。

2. 创建 Character 对象：

   可以通过构造器或自动装箱（autoboxing）将 char 值转换为 Character 对象。

char ch = 'a';
Character characterObject = new Character(ch); // 使用构造器
Character characterObject2 = ch; // 自动装箱

     3.常用方法：

• Character 类提供了许多实用方法来处理字符。例如：
• Character.isDigit(char ch): 检查字符是否为数字。
• Character.isLetter(char ch): 检查字符是否为字母。
• Character.toUpperCase(char ch): 将字符转换为大写。
• Character.toLowerCase(char ch): 将字符转换为小写。

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

class Solution {
    // 定义一个方法来查找字符串 s 中所有是字符串 p 的字母异位词的子串的起始索引
    public List<Integer> findAnagrams(String s, String p) {
        // 获取字符串 s 和 p 的长度
        int n = s.length(), m = p.length();
        // 结果列表，用于存储所有符合条件的起始索引
        List<Integer> res = new ArrayList<>();
        // 如果 s 的长度小于 p 的长度，直接返回空列表
        if(n < m) return res;
        // 定义两个数组，用于记录 p 和 s 当前窗口中字符的频率
        int[] pCnt = new int[26];
        int[] sCnt = new int[26];
        // 初始化频率数组，将 p 和 s 前 m 个字符的频率记录到各自的数组中
        for(int i = 0; i < m; i++){
            pCnt[p.charAt(i) - 'a']++;
            sCnt[s.charAt(i) - 'a']++;
        }
        // 检查初始窗口（s 的前 m 个字符）是否与 p 匹配，如果匹配，将索引 0 加入结果列表
        if(Arrays.equals(sCnt, pCnt)){
            res.add(0);
        }
        // 遍历字符串 s，从索引 m 开始，每次向右滑动一个字符
        for(int i = m; i < n; i++){
            // 移除左边界字符的频率（滑动窗口左移）
            sCnt[s.charAt(i - m) - 'a']--;
            // 添加右边界字符的频率（滑动窗口右移）
            sCnt[s.charAt(i) - 'a']++;
            // 检查当前窗口是否与 p 匹配，如果匹配，将起始索引加入结果列表
            if(Arrays.equals(sCnt, pCnt)){
                res.add(i - m + 1);
            }
        }
        // 返回结果列表
        return res;
    }
}

1. 初始化和边界检查：

   • 获取 s 和 p 的长度。
   • 如果 s 的长度小于 p 的长度，直接返回空列表，因为不可能有异位词。

2. 频率数组初始化：

   • 使用两个大小为 26 的数组 pCnt 和 sCnt 分别记录 p 和 s 当前窗口中字符的频率。
   • 初始化频率数组，记录 p 和 s 前 m 个字符（p 的长度）的频率。

3. 初始窗口匹配检查：

   • 检查 s 的前 m 个字符是否与 p 匹配，如果匹配，将索引 0 加入结果列表。

4. 滑动窗口遍历：

   • 从索引 m 开始遍历 s，每次滑动窗口右移一个字符：
     • 减少左边界字符的频率（移出窗口）。
     • 增加右边界字符的频率（加入窗口）。
     • 检查当前窗口是否与 p 匹配，如果匹配，将起始索引加入结果列表。

5. 返回结果：

   • 返回包含所有符合条件的起始索引的结果列表。

代码深度解释：

当 i 从 m 开始遍历到 n-1 时，代表滑动窗口的右边界每次右移一个字符，这两行代码分别是在这个过程中执行的操作。

1. sCnt[s.charAt(i - m) - 'a']--;：这行代码是为了移除左边界字符的频率。在滑动窗口右移时，窗口的左边界向右移动一个字符，因此需要将移出窗口的左边界字符在 sCnt 数组中的计数减去 1。

2. sCnt[s.charAt(i) - 'a']++;：这行代码是为了添加右边界字符的频率。在滑动窗口右移时，窗口的右边界向右移动一个字符，因此需要将新加入窗口的右边界字符在 sCnt 数组中的计数加上 1。

这两步操作保证了每次窗口的频率数组 sCnt 都能正确地反映当前窗口中字符的频率情况，以便后续比较是否与 p 的频率数组 pCnt 相同，从而判断是否满足异位词的条件。

class Solution {
    // 定义一个方法来查找字符串 s 中所有是字符串 p 的字母异位词的子串的起始索引
    public List<Integer> findAnagrams(String s, String p) {
        // 获取字符串 s 和 p 的长度
        int n = s.length(), m = p.length();
        // 结果列表，用于存储所有符合条件的起始索引
        List<Integer> res = new ArrayList<>();
        // 如果 s 的长度小于 p 的长度，直接返回空列表
        if (n < m) return res;

        // 定义两个数组，用于记录 p 和 s 当前窗口中字符的频率
        int[] pCnt = new int[26];
        int[] sCnt = new int[26];

        // 初始化 p 的频率数组，将 p 的每个字符的频率记录到 pCnt 数组中
        for (int i = 0; i < m; i++) {
            pCnt[p.charAt(i) - 'a']++;
        }

        // 定义左指针，初始值为 0
        int left = 0;
        // 遍历字符串 s，每次右指针右移一个字符
        for (int right = 0; right < n; right++) {
            // 获取右指针当前字符在字母表中的索引
            int curRight = s.charAt(right) - 'a';
            // 增加当前右指针字符在 sCnt 数组中的频率
            sCnt[curRight]++;
            
            // 如果当前右指针字符的频率超过了 p 中该字符的频率，需要缩小窗口
            while (sCnt[curRight] > pCnt[curRight]) {
                // 获取左指针当前字符在字母表中的索引
                int curLeft = s.charAt(left) - 'a';
                // 减少当前左指针字符在 sCnt 数组中的频率
                sCnt[curLeft]--;
                // 左指针右移一格
                left++;
            }

            // 如果当前窗口的长度等于 p 的长度，说明找到了一个异位词
            if (right - left + 1 == m) {
                // 将当前窗口的起始索引加入结果列表
                res.add(left);
            }
        }

        // 返回结果列表
        return res;
    }
}

这段代码使用了滑动窗口和字符频率计数技术来查找字符串 s 中所有是字符串 p 的字母异位词的子串的起始索引。具体操作如下：

1. 初始化和边界检查：

   • 获取 s 和 p 的长度。
   • 如果 s 的长度小于 p 的长度，直接返回空列表，因为不可能有异位词。

2. 频率数组初始化：

   • 使用一个大小为 26 的数组 pCnt 记录 p 中每个字符的频率。
   • 使用一个大小为 26 的数组 sCnt 来记录当前滑动窗口中字符的频率。

3. 滑动窗口遍历：

   • 使用两个指针 left 和 right 表示当前滑动窗口的左右边界。
   • 右指针 right 从 0 开始遍历 s，每次右移一个字符，将该字符在 sCnt 数组中的频率加 1。
   • 如果当前字符的频率超过了 p 中该字符的频率，进入 while 循环，通过移动左指针 left 来缩小窗口，直到当前字符的频率不超过 p 中该字符的频率为止。
   • 如果当前窗口的长度等于 p 的长度，说明找到了一个异位词，将窗口的起始索引 left 加入结果列表。

4. 返回结果：

   • 返回包含所有符合条件的起始索引的结果列表。