题目Given a strings, find the length of thelongest substringwithout repeating characters.Example 1:Input:s abcabcbbOutput:3Explanation:The answer is abc, with the length of 3.Example 2:Input:s bbbbbOutput:1Explanation:The answer is b, with the length of 1.Example 3:Input:s pwwkewOutput:3Explanation:The answer is wke, with the length of 3. Notice that the answer must be a substring, pwke is a subsequence and not a substring.Example 4:Input:s Output:0Constraints:0 s.length 5 * 104sconsists of English letters, digits, symbols and spaces.这题一看就觉得应该是sliding windowcheck了一下tag果然然后尝试着自己独立写代码居然一遍bug free过了感动得流下了菜鸡的泪水。思路就是用一个left pointer一个right pointer表示window再用一个hashset来存当前window中的字母保持left不动逐个试探移动right如果right对应的字母不在set中那很好可以直接加入set并比较求max。否则需要不断移动left并把left对应的字母从set中移除直到set中没有重复的字母为止或者left要超过right为止最后当然还是要把right对应的字母放入set并right。两种情况合并一下就是不管怎么样right都要加入set并。Runtime: 6 ms, faster than 76.19% of Java online submissions for Longest Substring Without Repeating Characters.Memory Usage: 39 MB, less than 98.39% of Java online submissions for Longest Substring Without Repeating Characters.class Solution { public int lengthOfLongestSubstring(String s) { if (s.length() 0) { return 0; } int left 0; int right 1; int maxLen 1; SetCharacter set new HashSet(); set.add(s.charAt(left)); while (right ! s.length()) { char c s.charAt(right); if (!set.contains(c)) { maxLen Math.max(maxLen, right - left 1); } else { while (left right set.contains(c)) { set.remove(s.charAt(left)); left; } } set.add(c); right; } return maxLen; } }然后看了solution发现人家几行就写完了的我写的好复杂。普通的solution直接while循环里面left n right n如果right不在set中就加入并移动right如果在就删除并移动left一个循环搞定只是一次循环只动一个指针而我是直接一次把所有left都动到不能再动为止其实总体思路是一样的。public class Solution { public int lengthOfLongestSubstring(String s) { int n s.length(); SetCharacter set new HashSet(); int ans 0, i 0, j 0; while (i n j n) { // try to extend the range [i, j] if (!set.contains(s.charAt(j))){ set.add(s.charAt(j)); ans Math.max(ans, j - i); } else { set.remove(s.charAt(i)); } } return ans; } }还有个更牛逼的方法就是用hashmap来存每个char对应的index这样我们就可以一次性把left移到已经存在的index之后了。这样优化以后之前最多是移动2n次左右各n次这下只需要移动n次了。甚至可以不用map用数组来表示ASCII……public class Solution { public int lengthOfLongestSubstring(String s) { int n s.length(), ans 0; MapCharacter, Integer map new HashMap(); // current index of character // try to extend the range [i, j] for (int j 0, i 0; j n; j) { if (map.containsKey(s.charAt(j))) { i Math.max(map.get(s.charAt(j)), i); } ans Math.max(ans, j - i 1); map.put(s.charAt(j), j 1); } return ans; } }public class Solution { public int lengthOfLongestSubstring(String s) { int n s.length(), ans 0; int[] index new int[128]; // current index of character // try to extend the range [i, j] for (int j 0, i 0; j n; j) { i Math.max(index[s.charAt(j)], i); ans Math.max(ans, j - i 1); index[s.charAt(j)] j 1; } return ans; } }2026.8.29时隔六年又是一点儿也不会。但是现在在练sliding window所以大概也在慢慢摸索套路了虽然还是思路不够灵活没想到需要用set来看有没有重复的char。有思路了也没有一次bug free啊。菜就多练。就现在学到的套路left 0right从0开始for loop。如果right已经在set里了那就挪left直到它不在了为止注意remove和的顺序。然后把right加进set里和做比较更新result。class Solution { public int lengthOfLongestSubstring(String s) { int left 0; int result 0; SetCharacter set new HashSet(); for (int right 0; right s.length(); right) { char c s.charAt(right); while (set.contains(c)) { set.remove(s.charAt(left)); left; } set.add(c); result Math.max(result, right - left 1); } return result; } }