hot100——滑动窗口

无重复字符的最长子串给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。示例 1:输入:s abcabcbb输出:3解释:因为无重复字符的最长子串是abc所以其长度为 3。注意 bca 和 cab 也是正确答案。示例 2:输入:s bbbbb输出:1解释:因为无重复字符的最长子串是b所以其长度为 1。示例 3:输入:s pwwkew输出:3解释:因为无重复字符的最长子串是wke所以其长度为 3。 请注意你的答案必须是子串的长度pwke是一个子序列不是子串。提示0 s.length 105s由英文字母、数字、符号和空格组成思路及解法用窗口[left, right]表示当前无重复的子串。right 向右扩大窗口如果遇到重复字符left 向右缩小窗口每次更新最大长度关键窗口内始终没有重复字符。输入s abcabcbb初始left0, window{}right0, ca: 加入 → window{a} 长度1right1, cb: 加入 → window{a,b} 长度2right2, cc: 加入 → window{a,b,c} 长度3right3, ca: a重复 → 删left的aleft1window{b,c} → 加入a → {b,c,a} 长度3right4, cb: b重复 → 删left的bleft2window{c,a} → 加入b → {c,a,b} 长度3right5, cc: c重复 → 删left的cleft3window{a,b} → 加入c → {a,b,c} 长度3right6, cb: b重复 → 删left的aleft4window{b,c} → b还重复 → 删left的bleft5window{c} → 加入b → {c,b} 长度2right7, cb: b重复 → 删left的cleft6window{b} → b还重复 → 删left的bleft7window{} → 加入b → {b} 长度1最大长度 3class Solution { public int lengthOfLongestSubstring(String s) { SetCharacter windownew HashSet(); int left0; int maxlen0; for(int right0;rights.length();right){ char cs.charAt(right); while(window.contains(c)){ window.remove(s.charAt(left)); left; } window.add(c); maxlenMath.max(maxlen,right-left1); } return maxlen; } }时间复杂度O(n)虽然有两层循环但 left 不会回退所以是 O(n)不是 O(n²)。空间复杂度O(k)k 是常数所以也可以说是 O(1)。找到字符串中所有字母异位词给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。示例 1:输入:s cbaebabacd, p abc输出:[0,6]解释:起始索引等于 0 的子串是 cba, 它是 abc 的异位词。 起始索引等于 6 的子串是 bac, 它是 abc 的异位词。示例 2:输入:s abab, p ab输出:[0,1,2]解释:起始索引等于 0 的子串是 ab, 它是 ab 的异位词。 起始索引等于 1 的子串是 ba, 它是 ab 的异位词。 起始索引等于 2 的子串是 ab, 它是 ab 的异位词。提示:1 s.length, p.length 3 * 104s和p仅包含小写字母思路及解法滑动窗口 字符计数窗口大小固定为p.length()。1. 统计 p 中每个字符的出现次数 → pcount[]2. 用滑动窗口遍历 s窗口大小为 p.length()3. 统计窗口内每个字符的出现次数 → scount[]4. 如果 scount pcount说明找到一个异位词输入s cbaebabacd,p abcp abcpcount {a:1, b:1, c:1}窗口大小 3right0: 窗口[c]scount{c:1} 不匹配right1: 窗口[c,b]scount{c:1,b:1} 不匹配right2: 窗口[c,b,a]scount{c:1,b:1,a:1} 匹配 ✅ 索引0right3: 窗口[b,a,e]scount{b:1,a:1,e:1} 不匹配right4: 窗口[a,e,b]scount{a:1,e:1,b:1} 不匹配right5: 窗口[e,b,a]scount{e:1,b:1,a:1} 不匹配right6: 窗口[b,a,b]scount{b:2,a:1} 不匹配right7: 窗口[a,b,a]scount{a:2,b:1} 不匹配right8: 窗口[b,a,c]scount{b:1,a:1,c:1} 匹配 ✅ 索引6right9: 窗口[a,c,d]scount{a:1,c:1,d:1} 不匹配结果[0, 6]class Solution { public ListInteger findAnagrams(String s, String p) { ListInteger resultnew ArrayList(); if(s.length()p.length()){ return result; } int[] scountnew int[26]; int[] pcountnew int[26]; for(char c:p.toCharArray()){ pcount[c-a]; } int left0; for(int right0;rights.length();right){ scount[s.charAt(right)-a]; if((right-left1)p.length()){ scount[s.charAt(left)-a]--; left; } if((right-left1)p.length()){ if(Arrays.equals(scount,pcount)){ result.add(left); } } } return result; } }时间复杂度O(n)空间复杂度O(1)来源力扣LeetCode