Leetcode连续不重复最长子串长度心得

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
暴力法：o（n2）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        List<Integer> record_len = new ArrayList<Integer>();
        List<Character> substr;
        if(length == 0)return 0;
        for(int i=0; i<length;i++){
            substr = new ArrayList<Character>();
            int len = 1;
            substr.add(s.charAt(i));
            for(int j=i+1; j<length; j++){
                if(substr.contains(s.charAt(j))){
                    break;
                }
                else{
                   substr.add(s.charAt(j));
                   len += 1;
                }
            }
            record_len.add(len);
        }
        int max = record_len.get(0);
        // for(int i=0;i<record_len.size();i++){
        //     max = max>record_len.get(i)?max:record_len.get(i);
        // }
        return Collections.max(record_len);
    }
}

优化的滑动串口方法：o(n)

class Solution {//o(n)
    public int lengthOfLongestSubstring(String s) {
           int length = s.length();
           int ans = 0;
           Map<Character,Integer> map = new HashMap<Character,Integer>();
           for(int i=0,j=0;j<length;j++){
                if(map.containsKey(s.charAt(j))){//Key,Upper
                    i = Math.max(map.get(s.charAt(j)), i);
                }
                map.put(s.charAt(j), j+1);//continue to insert data 
                ans = Math.max(ans, j-i+1);
           }
        return ans;
    }
}