LeetCode 3

---

公司只能访问LeetCode国际，所以题目是英文

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

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

Example 2:

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

Example 3:

Input: s = “pwwkew” Output: 3 Explanation: 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

s consists of English letters, digits, symbols and spaces.

Related Topics

Hash TableTwo PointersStringSliding Window

---

方法一

public int lengthOfLongestSubstring(String s) { int n = s.length(); int max = 0; // end，start两个指针维护一个滑动窗口 int end =0 , start = 0; // 使用HashSet储存最长连续不重复子串 HashSet<Character> hashSet = new HashSet<>(); while(end < n && start < n){ /* 后看if判断语句 当Hashset中存在该字符时，end指针不动，（此时没有把end指针对应的字符存进HashSet） 删除start指针对应字符，并让start后移，这实际就是把HashSet清空了 但是max已经记录了最大值 */ if(hashSet.contains(s.charAt(end))){ hashSet.remove(s.charAt(start++)); }else{ /* 先看else中的存储部分 当HashSet中不存在该字符时，保存该字符并使end指针后移一位 然后比较出最长连续不重复子串：max */ hashSet.add(s.charAt(end++)); max = Math.max(max,end - start); } } return max; }

---

方法二

两个方法的思路其实差不多，使用的容器不同，方法一中HashSet就是实际的滑动窗口，即时更新，此处使用HashMap则是通过键值对的方法，把字符存为key，字符的下一个位置存为value，然后用两个指针维护“value的滑动窗口”。

public int lengthOfLongestSubstring(String s) { int n = s.length(); int max = 0; int end=0,start=0; Map<Character,Integer> map=new HashMap<>(); for(;start<n && end<n;end++){ /* 后看if判断语句 当HashMap中存在该字符时，开始移动start。 给start赋值：max（已存在字符在HashMap中的位置，原start的下一个位置） 这就是为什么存的时候会有end+1，为了让start从重复的下一个位置开始。 */ if(map.containsKey(s.charAt(end))){ start=Math.max(map.get(s.charAt(end)),start);//从有重复的下一个位置继续找 } /* 依旧先看存储部分 在HashMap中顺序存储（字符值，顺序的下一个） 比较出最长连续不重复子串：max 使用end-start+1的原因是for循环，循环执行一次后end++，方法一中语句执行后就加一了， 第一个值存进去会出现end=0，start=0，end-start=0，所以此处end-start+1 */ map.put(s.charAt(end),end+1); max=Math.max(max,end-start+1); } return max; }