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封装为对象，使其能够在需要对象的上下文中使用。创建
可以通过构造器或自动装箱（autoboxing）将Character对象：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']++;
}
// 定义左指针，初始值为 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的字母异位词的子串的起始索引。具体操作如下：
初始化和边界检查：
- 获取
s和p的长度。- 如果
s的长度小于p的长度，直接返回空列表，因为不可能有异位词。频率数组初始化：
- 使用一个大小为 26 的数组
pCnt记录p中每个字符的频率。- 使用一个大小为 26 的数组
sCnt来记录当前滑动窗口中字符的频率。滑动窗口遍历：
- 使用两个指针
left和right表示当前滑动窗口的左右边界。- 右指针
right从 0 开始遍历s，每次右移一个字符，将该字符在sCnt数组中的频率加 1。- 如果当前字符的频率超过了
p中该字符的频率，进入while循环，通过移动左指针left来缩小窗口，直到当前字符的频率不超过p中该字符的频率为止。- 如果当前窗口的长度等于
p的长度，说明找到了一个异位词，将窗口的起始索引left加入结果列表。返回结果：
- 返回包含所有符合条件的起始索引的结果列表。
