尧图网站建设 
3. 无重复字符的最长子串 - 力扣LeetCodeclass Solution { public int lengthOfLongestSubstring(String s) { // 1. 创建一个哈希集合 occ用于记录当前滑动窗口中已经出现的字符。 // 目的是实现 O(1) 时间复杂度的字符存在性检查。 SetCharacter occ new HashSetCharacter(); 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. 找到字符串中所有字母异位词 - 力扣LeetCodeclass Solution { public ListInteger findAnagrams(String s, String p) { // 1. 获取两个字符串的长度 int sLen s.length(), pLen p.length(); // 2. 如果 s 比 p 短不可能包含 p 的异位词直接返回空列表 if (sLen pLen) { return new ArrayListInteger(); } // 3. 初始化结果列表 ans ListInteger ans new ArrayListInteger(); // 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. 检查当前窗口从 i1 开始长度为 pLen是否与 p 是异位词 // 如果频率数组相同则当前窗口的起始索引 i1 是一个答案 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为0d为1。比较时在索引0处a的位置sCount是0而pCount是1两者不等方法立即返回false不会继续比较后面的元素。 LeetCode Hot 100 题目详解-滑动窗口
3. 无重复字符的最长子串 - 力扣LeetCodeclass Solution { public int lengthOfLongestSubstring(String s) { // 1. 创建一个哈希集合 occ用于记录当前滑动窗口中已经出现的字符。 // 目的是实现 O(1) 时间复杂度的字符存在性检查。 SetCharacter occ new HashSetCharacter(); 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. 找到字符串中所有字母异位词 - 力扣LeetCodeclass Solution { public ListInteger findAnagrams(String s, String p) { // 1. 获取两个字符串的长度 int sLen s.length(), pLen p.length(); // 2. 如果 s 比 p 短不可能包含 p 的异位词直接返回空列表 if (sLen pLen) { return new ArrayListInteger(); } // 3. 初始化结果列表 ans ListInteger ans new ArrayListInteger(); // 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. 检查当前窗口从 i1 开始长度为 pLen是否与 p 是异位词 // 如果频率数组相同则当前窗口的起始索引 i1 是一个答案 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为0d为1。比较时在索引0处a的位置sCount是0而pCount是1两者不等方法立即返回false不会继续比较后面的元素。