﻿ leetcode 3 Longest Substring Without Repeating Characters

leetcode 3 Longest Substring Without Repeating Characters

lc3 Longest Substring Without Repeating Characters

hashmap，

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

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

containsKey(s.charAt(i))

``` 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 }```

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 }```