leetcode 003. Longest Substring Without Repeating Characters

题目链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/

原题描述：

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

Example 1:

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

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

Input: "pwwkew"
Output: 3
Explanation: 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）

：滑动窗口，res记录最大无重复子串的长度，start为最大无重复子串的前一位，保证一个窗口向后移，每向后查找一个字符，看map中是否包含（查看包含的方法为该字符在map中的位置是否大于start），如果包含则更新该字符在map中的值（即位置）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int res = 0,start=-1;
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<len;++i){
            char c = s.charAt(i);
            if(map.containsKey(c)&&map.get(c)>start){//查看map中是否含有并且在当前子串中
                start=map.get(c);//如果在，则更新start位置，代表将左边字符移走
            }
            map.put(c,i);//更新在map中的位置
            res= Math.max(res,i-start);//找出最长子串
        }
        return res;
    }
}

方法二（用set）：

用了set集合元素的不重复性，right代表右边界+1，left表示最长子串左边界,当循环一次时候，判断是否在set集合中，在，就将其从left开始删除，直到删除到该字符为止，否则将该字符添加到set中

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int left=0,right=0;//left表示最长子串左边界，right为右边界+1
        int res = 0;
        Set<Character> set = new HashSet<>();
        while(right<len){
            char c = s.charAt(right);
            if(set.contains(c)){
               set.remove(s.charAt(left++));//一直移除，直到set中不包含c字符
            }else{
                set.add(c);
                right++;
            }
            res = Math.max(res,right-left);//获取最大长度
        }
        return res;
    }
}

方法三（数组）：

以上两种方法都是存字符，下面这种方法，将字符在AscII码中的位置存入数组，将值为该字符最晚出现的位置，每次循环记录字符出现的位置，并将其存入数组，如果该字符之前出现过，更新left位置，即字符的最左边界，依次循环即可。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0)  return 0;
        
        int[] occur = new int[128];
        Arrays.fill(occur, -1);
        
        int left = -1, right = 0, prev = -1, res = 0;
        for(right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            prev = occur[c];//记录该字符出现的位置
            occur[c] = right;//先存入该字符
            
            if(prev != -1) {//如果该字符出现过
                left = Math.max(prev, left);//更新left位置为这个字符最后出现的位置
            }
            res = Math.max(res, right - left);//每次循环结束，都要找出res最大值
        }
        return res;
    }
}