leetcode 3 Longest Substring Without Repeating Characters

lc3 Longest Substring Without Repeating Characters

思路就是，每次碰到出现第二次的字符时，更新maxLen,并且从该字符第一次出现位置后一个字母继续计算满足题意的子串长度

法一：

hashmap，

key放字母，用来检查是否出现过

value放key这个字母上一次出现的位置

containsKey(s.charAt(i))

若不存在，将(key, key的位置)放入hashmap

若存在，则计算当前子串的长度（当前i减去该key所指value），与maxLen比较

并把i更新为key所指value，并将hashmap重新初始化

 1 class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         //if(s == null || s.length() == 0)
 4           //  return 0;
 5         
 6         HashMap<Character, Integer> map = new HashMap<>();
 7         int maxLen = 0;
 8         int count = 0;
 9         
10         for(int i=0; i<s.length(); i++){
11             if(!map.containsKey(s.charAt(i))){
12                 map.put(s.charAt(i), i);
13                 count++;
14             }else{
15                 maxLen = Math.max(maxLen, count);
16                 count = 0;
17                 i = map.get(s.charAt(i));
18                 map = new HashMap<Character, Integer>();
19             }
20         }
21         
22         return Math.max(maxLen, count);
23     }
24 }

法二：

双指针，

思路是一样的，碰到第二次出现的字符，更新maxLen，从该字符第一次出现位置继续计算子串长度

只不过，用一个count[256]代替hashmap的key功能

begin和end代替hashmap的value功能

 1 class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         
 4         int[] count = new int[256];
 5         int maxLen = 0;
 6         
 7         int begin = 0;
 8         int end = 0;
 9         
10         while(end < s.length()){
11             if(count[s.charAt(end)] != 0){
12                 maxLen = Math.max(maxLen, end - begin);
13                 while(s.charAt(begin) != s.charAt(end))
14                     count[s.charAt(begin++)]--;
15                 begin++;
16                 count[s.charAt(end)]--;
17             }
18             count[s.charAt(end++)]++;
19         }
20         return Math.max(maxLen, end - begin);
21     }
22 }

leetcode 3 Longest Substring Without Repeating Characters

推荐阅读