力扣滑动窗口题目总结

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）来寻找最长的无重复字符子串。具体操作如下：

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

补充知识点：

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

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

封装基本类型 char：

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

创建 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;}
}

初始化和边界检查：

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

频率数组初始化：

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

初始窗口匹配检查：

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

滑动窗口遍历：

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

返回结果：

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

代码深度解释：

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

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

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']++;}// 定义左指针，初始值为 0int 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 的字母异位词的子串的起始索引。具体操作如下：

初始化和边界检查：

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

频率数组初始化：

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

滑动窗口遍历：

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

返回结果：

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