LeetCode Hot 100 题目详解-滑动窗口
3. 无重复字符的最长子串 - 力扣（LeetCode）
class Solution { public int lengthOfLongestSubstring(String s) { // 1. 创建一个哈希集合 occ，用于记录当前滑动窗口中已经出现的字符。 // 目的是实现 O(1) 时间复杂度的字符存在性检查。 Set<Character> occ = new HashSet<Character>(); int n = s.length(); // 2. 初始化右指针 rk 为 -1，表示窗口的右边界在字符串起始位置的左侧。 // ans 用于记录遍历过程中找到的最长无重复子串的长度。 int rk = -1, ans = 0; // 3. 外层 for 循环，i 作为左指针，遍历字符串的每个位置。 for (int i = 0; i < n; ++i) { // 4. 当 i != 0 时，说明左指针已经向右移动了。 // 在移动左指针之前，需要将集合中上一个左指针指向的字符（即 s.charAt(i-1)）移除。 // 这保证了集合中始终只存储当前窗口 [i, rk] 内的字符。 if (i != 0) { occ.remove(s.charAt(i - 1)); } // 5. 内层 while 循环，尝试不断向右移动右指针 rk。 // 循环条件：rk + 1 未超出字符串范围，且 s.charAt(rk + 1) 不在集合中。 // 这表示我们可以安全地将新字符纳入当前窗口，而不会产生重复。 while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) { // 6. 将新字符添加到集合中，表示它现在在窗口内。 occ.add(s.charAt(rk + 1)); // 7. 右指针实际向右移动一位。 ++rk; } // 8. 当 while 循环结束时，说明 [i, rk] 是以 i 为左边界时，能得到的极长无重复字符子串。 // 计算当前窗口长度 (rk - i + 1)，并更新全局最大值 ans。 ans = Math.max(ans, rk - i + 1); } // 9. 返回最终计算出的最长长度。 return ans; } }核心思路与关键点
核心思路：使用滑动窗口（双指针）和哈希集合。滑动窗口始终维护一个不包含重复字符的子串。通过不断移动右指针扩展窗口，当遇到重复字符时，移动左指针缩小窗口，直到重复字符被移除，从而在 O(n) 时间内找到所有可能的无重复子串并记录最大值。
指针逻辑：
右指针 (
rk)：负责探索新字符，只要新字符不重复就不断右移，扩大窗口。左指针 (
i)：负责在遇到重复时缩小窗口。每次循环开始前，都会移除左指针前一个位置的字符，保证了窗口的合法性。
正确性：该算法保证了每个字符作为左边界时，都能找到以它为起点的最长无重复子串，因此最终答案涵盖了所有情况。由于左右指针都只会单向移动，整体时间复杂度为 O(n)。
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集的大小（即可能出现的不同字符数量），因为哈希集合最多存储整个字符集。
核心思路与关键点
核心思路：使用固定大小的滑动窗口和字符频率数组。因为题目要求找的是字母异位词（字母种类和数量相同，顺序无关），所以可以用一个长度为 26 的数组来记录每个字母的出现次数，通过比较数组是否相等来判断是否为异位词。
滑动窗口：窗口大小固定为
pLen（字符串 p 的长度）。每次窗口向右滑动一步时，移除左侧字符，添加右侧新字符，并更新频率数组，实现 O(1) 时间更新窗口状态。时间与空间复杂度：
时间复杂度：O(n + m)，其中 n 和 m 分别是字符串 s 和 p 的长度。只需遍历一次 s 和一次 p，每次比较数组是 O(1)（因为数组长度固定为 26）。
空间复杂度：O(1)，只使用了两个固定大小的数组和结果列表。
关键方法
Arrays.equals：这是比较两个int[]数组内容是否相同的便捷方法，简化了代码。
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
class Solution { public List<Integer> findAnagrams(String s, String p) { // 1. 获取两个字符串的长度 int sLen = s.length(), pLen = p.length(); // 2. 如果 s 比 p 短，不可能包含 p 的异位词，直接返回空列表 if (sLen < pLen) { return new ArrayList<Integer>(); } // 3. 初始化结果列表 ans List<Integer> ans = new ArrayList<Integer>(); // 4. 创建两个长度为 26 的数组，用于统计字符频率 // sCount 记录当前窗口中字符的出现次数，pCount 记录 p 中字符的出现次数 int[] sCount = new int[26]; int[] pCount = new int[26]; // 5. 第一次遍历：统计 p 中字符频率，并初始化 s 中第一个长度为 pLen 的窗口 for (int i = 0; i < pLen; ++i) { ++sCount[s.charAt(i) - 'a']; // 将 s 的前 pLen 个字符加入窗口 ++pCount[p.charAt(i) - 'a']; // 统计 p 中每个字符的出现次数 } // 6. 检查初始窗口（s 的前 pLen 个字符）是否与 p 是异位词 // 如果两个频率数组完全相同，说明找到了一个异位词，起始索引为 0 if (Arrays.equals(sCount, pCount)) { ans.add(0); } // 7. 滑动窗口：从索引 0 开始，向右滑动，直到窗口右边界到达 s 的末尾 for (int i = 0; i < sLen - pLen; ++i) { // 8. 窗口右移一步： // 移除窗口最左边的字符（索引 i），对应频率减 1 --sCount[s.charAt(i) - 'a']; // 添加窗口右边的新字符（索引 i + pLen），对应频率加 1 ++sCount[s.charAt(i + pLen) - 'a']; // 9. 检查当前窗口（从 i+1 开始，长度为 pLen）是否与 p 是异位词 // 如果频率数组相同，则当前窗口的起始索引 i+1 是一个答案 if (Arrays.equals(sCount, pCount)) { ans.add(i + 1); } } // 10. 返回所有找到的起始索引 return ans; } }核心思路与关键点
核心思路：使用固定大小的滑动窗口和字符频率数组。因为题目要求找的是字母异位词（字母种类和数量相同，顺序无关），所以可以用一个长度为 26 的数组来记录每个字母的出现次数，通过比较数组是否相等来判断是否为异位词。
滑动窗口：窗口大小固定为
pLen（字符串 p 的长度）。每次窗口向右滑动一步时，移除左侧字符，添加右侧新字符，并更新频率数组，实现 O(1) 时间更新窗口状态。时间与空间复杂度：
时间复杂度：O(n + m)，其中 n 和 m 分别是字符串 s 和 p 的长度。只需遍历一次 s 和一次 p，每次比较数组是 O(1)（因为数组长度固定为 26）。
空间复杂度：O(1)，只使用了两个固定大小的数组和结果列表。
关键方法
Arrays.equals：这是比较两个int[]数组内容是否相同的便捷方法，简化了代码。
这个解法是解决“字符串异位词”问题的标准模板，通过固定窗口和频率统计，高效地找到了所有匹配的起始索引。如果对代码细节或算法证明有疑问，可以随时提出。
if (Arrays.equals(sCount, pCount)) { ans.add(0); }怎么比较的
Arrays.equals(sCount, pCount)这一行，是代码中非常关键的一步。它不是在比较两个数组变量是否指向同一个对象，而是比较两个数组的“内容”是否完全相同。
1. 它是如何比较的？
Arrays.equals()方法是 Java 标准库提供的一个工具方法，专门用来比较两个一维数组。对于int[]类型的数组，它的比较逻辑是逐元素（Element-wise）比较，非常严格：
首先检查引用：如果两个数组引用指向同一个对象（即
sCount == pCount），直接返回true。检查 null：如果任何一个数组为
null，返回false。检查长度：如果两个数组的长度不同，返回
false。逐元素比较：如果长度相同，它会用一个循环，从索引
0开始，逐个比较两个数组对应位置上的int值是否相等。只要发现任何一个位置的值不相等，就立即返回false。只有当所有对应位置的值都完全相等时，才返回true。
在你的代码中，sCount和pCount都是长度为 26 的int[]数组。所以Arrays.equals(sCount, pCount)实际上在做一个快速的、按顺序的逐项检查，确认当前窗口中 26 个字母（'a' 到 'z'）的出现次数是否和模式串p中的完全一致。
2. 结合你的代码理解
在findAnagrams方法里，这行代码出现在两个地方，作用是一样的：
初始化窗口检查：在第一次构建完初始窗口后，用它来检查
s的前pLen个字符组成的子串，是否是p的异位词。滑动窗口后检查：在每次窗口向右滑动一步并更新
sCount后，用它来检查新的当前窗口是否与p是异位词。
3. 一个简单的对比示例
假设p = "abc"，那么pCount会是[1, 1, 1, 0, 0, ...]（索引0的 'a' 为1，索引1的 'b' 为1，索引2的 'c' 为1）。
情况1（匹配）：当前窗口
sCount为"cba"，其统计为[1, 1, 1, 0, 0, ...]。Arrays.equals()会从索引0开始比较，发现每个位置都相同，返回true。情况2（不匹配）：当前窗口
sCount为"cbd"，其统计为[0, 1, 1, 1, 0, ...]（'a'为0，'d'为1）。比较时，在索引0处（'a'的位置），sCount是0，而pCount是1，两者不等，方法立即返回false，不会继续比较后面的元素。