008无重复字符的最长子串

无重复字符的最长子串题目链接https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public int lengthOfLongestSubstring(String s) { int length s.length(); if(length0){ return 0; } MapCharacter,Integer map new HashMap(length);//维护每个字符最近出现的下标 int l0, rl1, indexl; int ans1; map.put(s.charAt(0),0); while(rlength){ while(rlength!map.containsKey(s.charAt(r))){ map.put(s.charAt(r),r); r; } ansMath.max(ans,r-l); if(rlength){ break; } indexmap.get(s.charAt(r))1; while(lindex){ map.remove(s.charAt(l)); } map.put(s.charAt(r),r); r; } return ans; }分析代码的时间复杂度为O(n)空间复杂度为O(∣Σ∣)其中 Σ 表示字符集即字符串中可以出现的字符。我的思路是利用HashMap存储每次访问过的字符并维护这个字符最近出现的位置再利用两个指针l和r指向未重复字符串的起始位置r从l的下一个位置开始往右移动直到遇到HashMap中重复的字符更新答案然后让l移动到重复字符最近出现的位置的后一个位置并同步删除HashMap中字符的记录最后更新重复字符最近出现的记录即可。看了官方题解后的解答public int lengthOfLongestSubstring(String s) { int length s.length(); if(length0){ return 0; } SetCharacter set new HashSet(); int l,r; int ans0; set.add(s.charAt(0)); for(l0,rl1; rlength; l){ while(rlength!set.contains(s.charAt(r))){ set.add(s.charAt(r)); r; } ansMath.max(ans,r-l); if(rlength){ break; } set.remove(s.charAt(l)); } return ans; }分析​ 1、代码的时间复杂度为O(n)空间复杂度为O(∣Σ∣)其中 Σ 表示字符集即字符串中可以出现的字符。​ 2、采用滑动窗口。​ 3、用HashSet记录字符。​ 4、思路根据每一个字符当作开头时最长的字符串的长度取最大值即为答案。且满足“当以索引为k的字符作为开头时假设直到kn才遇到重复的字符那么以k1开头的字符串直到kn-1都不会遇到重复的字符”根据这个条件我们可以实现一直往后遍历而不会回退的情况从而实现O(n)的时间复杂度解决问题。​ 5、我的解答与官方解答的区别在于我用hashSet不仅保存了字符还维护了字符最近出现位置的索引每一次遇到重复字符后我选择直接跳到这个字符最近出现的位置而非将每一个元素都当作一次字符串的开头计算一遍。​ 6、经过与官方题解比较发现我才用的方法更符合双指针的特点。总结本题主要是采用滑动窗口哈希表解题用哈希表避免重复用滑动窗口维护以每一个元素作为开头的最长无重复子串。