企业官网建设流程全解析

题目：

Given a strings, find the length of thelongest substringwithout repeating characters.

Example 1:

Input:s = "abcabcbb"Output:3Explanation:The answer is "abc", with the length of 3.

Example 2:

Input:s = "bbbbb"Output:1Explanation:The answer is "b", with the length of 1.

Example 3:

Input:s = "pwwkew"Output: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:0

Constraints:

• 0 <= s.length <= 5 * 104
• sconsists of English letters, digits, symbols and spaces.

这题一看就觉得应该是sliding window，check了一下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; Set<Character> 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(); Set<Character> 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; Map<Character, 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 = 0，right从0开始for loop。如果right已经在set里了，那就挪left直到它不在了为止，注意remove和++的顺序。然后把right加进set里和做比较更新result。

class Solution { public int lengthOfLongestSubstring(String s) { int left = 0; int result = 0; Set<Character> 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; } }