【滑动窗口】【中等】无重复字符的最长字串

题目给定一个字符串 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 10^5s 由英文字母、数字、符号和空格组成方法一暴力枚举枚举所有子串例如s “abcabcbb”则枚举a、ab、abc、abca、abcab…然后判断是否有重复时间复杂度O(n³)publicstaticintlengthOfLongestSubstring(Strings){intmax0;intleft0;HashSetCharacterhashsetnewHashSet();for(intright0;rights.length();right){while(hashset.contains(s.charAt(right))){hashset.remove(s.charAt(left));left;}hashset.add(s.charAt(right));maxMath.max(max,right-left1);}returnmax;}方法二滑动窗口维护一个 [left,right] 表示当前合法窗口。right遇到重复的就让left向右移动直到不重复为止每次比较计算窗口长度。publicstaticintlengthOfLongestSubstring(Strings){intmax0;intleft0;HashSetCharacterhashsetnewHashSet();for(intright0;rights.length();right){while(hashset.contains(s.charAt(right))){hashset.remove(s.charAt(left));left;}hashset.add(s.charAt(right));maxMath.max(max,right-left1);}returnmax;}方法三滑动窗口 HashMap跳跃上面的 HashSet 方法遇到重复串比如 aaaa 需要 left、left、left一步一步删除。但是 HashMap 可以直接跳。HashMap中存储如下例key是单位字符value记录该字符的最近下位置//字符:最近位置 a:0b:1c:2publicstaticintlengthOfLongestSubstring(Strings){HashMapCharacter,IntegermapnewHashMap();intleft0;intmax0;for(intright0;rights.length();right){charcs.charAt(right);if(map.containsKey(c)){//直接移动到重复位置的下一位//需要取最大值防止left回退leftMath.max(left,map.get(c)1);}//更新字符位置map.put(c,right);maxMath.max(max,right-left1);}returnmax;}