问题：

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring

解决：

① 使用map保存当前节点的值和到当前节点位置，共遍历了多少个字符，然后使用一个变量left记录左侧第一个不重复的字符的位置，从而可以计算当前不重复字符的个数（i - left + 1）.

class Solution { //65ms

    public int lengthOfLongestSubstring(String s) {         Map<Character,Integer> map = new HashMap<>();         int count  = 0;         int left = 0;         int right = 0;         while(right < s.length()) {             if(! map.containsKey(s.charAt(right)) || map.get(s.charAt(right)) < left){                 count = Math.max(count,right - left + 1);             }else{                 left = map.get(s.charAt(right));             }             map.put(s.charAt(right),right + 1);             right ++;         }         return count;     } }

class Solution { //54ms

    public int lengthOfLongestSubstring(String s) {         Map<Character,Integer> map = new HashMap<>();         int count  = 0;         int left = 0;         for (int i = 0;i < s.length() ;i ++ ) {             if(! map.containsKey(s.charAt(i)) || map.get(s.charAt(i)) <= left){//第二个条件表示重复字符在左边界外面                 count = Math.max(count,i - left + 1);             }else{                 left = map.get(s.charAt(i));             }             map.put(s.charAt(i),i + 1);         }         return count;     } }

② 然后我想到了用hash table保存，然后使用一个变量left记录下一个无重复的点。

class Solution { // 41ms

    public int lengthOfLongestSubstring(String s) {         int[] hash = new int[256];         int count = 0;         int left = 0;         for (int i = 0;i < s.length() ;i ++ ) {             if(hash[(int)s.charAt(i)] == 0 || hash[(int)s.charAt(i)] <= left){                 count = Math.max(count,i - left + 1);             }else{                 left = hash[(int)s.charAt(i)];             }             hash[(int)s.charAt(i)] = i + 1;         }           return count;     } }

③ 进化版

class Solution { //43ms

    public int lengthOfLongestSubstring(String s) {         int[] hash = new int[256];         Arrays.fill(hash,-1);         int count = 0;         int left = -1;         for (int i = 0;i < s.length() ;i ++ ) {             left = Math.max(left,hash[(int)s.charAt(i)]);             hash[(int)s.charAt(i)] = i;             count = Math.max(count,i - left);         }         return count;     } }

④ 使用hashset。把出现过的字符都放入set中，遇到set中没有的字符就加入set中并更新结果count，如果遇到重复的，则从左边开始删字符，直到删到重复的字符停止。

class Solution { //73ms

    public int lengthOfLongestSubstring(String s) {         int count = 0;         int left = 0;         int right = 0;         Set<Character> set = new HashSet<>();         while(right < s.length()){             if(! set.contains(s.charAt(right))){                 set.add(s.charAt(right));                 right ++;                 count = Math.max(count,set.size());             }else{                 set.remove(s.charAt(left));                 left ++;             }         }         return count;     } }