LeetCode热题100（Java）（3）滑动窗口

本章包括的题目有3. 无重复字符的最长子串 - 力扣LeetCode438. 找到字符串中所有字母异位词 - 力扣LeetCode1.无重复字符的最长子串思路解析要在一个字符串中找出最长的不含重复字符的子串只需维护一个内部无重复的“窗口”在遍历过程中不断扩展并调整这个窗口同时记录它曾经达到的最大长度。由于字符集有限题目使用标准 ASCII共 128 个可以用一个长度为 128 的计数数组来快速判断当前窗口内某个字符是否重复出现。算法使用左右指针 l 和 r 表示窗口的边界。一开始两者都在起始位置计数数组全为零。右指针 r 依次向右移动每次将新进入窗口的字符 s[r] 的计数加 1。如果该字符的计数超过 1说明这个字符在窗口内重复了由于只有新加入的字符可能造成重复此时就不断右移左指针 l并把离开窗口的字符计数减 1直到该重复字符的计数降回 1窗口重新成为无重复子串。每得到一个无重复的窗口就用它的长度 r - l 1 更新历史最大值 ret。当右指针遍历完整个字符串ret 就是最长无重复子串的长度。代码实现class Solution { public int lengthOfLongestSubstring(String s) { int ret 0; int len s.length(); int l 0,r 0; int[] arr new int[128]; for (;r len; r) { arr[s.charAt(r)]; while(arr[s.charAt(r)] 1){ arr[s.charAt(l)]--; l ; } ret Math.max(ret, (r - l 1)); } return ret; } }时间复杂度On空间复杂度O12.找到字符串中所有字母异位词思路解析要在字符串 s 中找出所有与 p 互为字母异位词的子串的起始索引只需用固定大小的滑动窗口在 s 上移动并比较窗口内字符的频数与 p 的频数是否相同。由于题目只涉及小写字母字符集大小固定为 26可以用两个长度为 26 的整数数组分别记录 p 的字符频数和当前窗口的字符频数。首先统计 p 中每个字母的出现次数存入 count。然后初始化一个长度为 |p| 的窗口但预先只将前 |p|-1 个字符的计数填入 count2这样后续循环中就能自然地完成“加入右边界 → 比较 → 移除左边界”的固定节奏。若 count2 与 count 完全相等使用 Arrays.equals 比较说明当前窗口内的子串是 p 的一个字母异位词把窗口的起始索引 i - |p| 1 加入结果列表。比较完成后将窗口左边界字符同样是 i - |p| 1的计数减 1为下一轮滑动做好准备。遍历结束结果列表即为所有异位词子串的起始位置。代码实现class Solution { public ListInteger findAnagrams(String s, String p) { if(p.length() s.length())return new ArrayList(); ListInteger ret new ArrayList(); char[] pp p.toCharArray(); int[] count new int[26]; for(char c: pp){ count[c - a] ; } int[] count2 new int[26]; for (int i 0; i p.length() - 1; i) { count2[s.charAt(i) - a]; } for (int i p.length() - 1; i s.length(); i) { count2[s.charAt(i) - a]; if(Arrays.equals(count,count2))ret.add(i - p.length() 1); count2[s.charAt(i - p.length() 1) - a] --; } return ret; } }补充Arrays.equals(count,count2) 可以比较两个数组是否相同但是 count.equals(count2) 只能比较两者的内存地址引用时间复杂度On空间复杂度O1上一章LeetCode热题100Java2双指针-CSDN博客