LeetCode：3. 无重复字符的最长子串

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

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

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

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

第一种解答：
思路：
使用一个长度为 128 的 boolean 数组 flag 充当散列表用来记录子串的字符（利用到字符的 ascii 码作为数组的下标），初始化都为false。遍历整个字符串，外循环控制子串的起始，内循环控制子串的长度，每遇到一个字符就检查 flag 中是否存在该元素，不存在则将 flag[]设置为 true，存在则结束内循环。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        boolean[] flag = new boolean[128]; // 问题1
        int  sublen = 0;
        for(int i = 0; i < s.length(); i ++){
            // 将 flag 初始化为 false
            for(int k = 0; k < flag.length; k++)
                flag[k] = false;
            // 子串的起始
            flag[(int)(s.charAt(i))] = true;
            int len = 1;
            for(int j = i+1; j < s.length(); j ++){
              // flag 中存在相同字符的情况  
              if(flag[(int)(s.charAt(j))])
                    break;
               // flag不存在相同字符的情况
               len ++;
               flag[(int)(s.charAt(j))] = true;
            }
            if(sublen < len){
                sublen = len;
            }
        }
        return sublen;
    }

}

也可将 boolean 数组换成 int 数组，数组记录的是元素所在的下标。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.equals("")) return 0;

        int[] flag = new int[128];
        int sublen = 0 ,len;
        for(int i = 0; i < s.length(); i ++ ){
            
            // 初始化 flag;
            for(int k = 0; k < flag.length; k++)
                flag[k] = -1;

            flag[s.charAt(i)] = i;
            len = 1;
            for(int j = i + 1; j < s.length(); j ++){
                if(flag[s.charAt(j)] != -1){
                    i = flag[s.charAt(j)];
                    break;
                }
                len ++;
                flag[s.charAt(j)] = j;
            }
            sublen = len > sublen ? len: sublen;
        }
        return sublen;
    }
}

参考评论区的第二种解答
第二种解答：
使用双指针 left, right维护一个无重复字符区间（left 与 right 之间的字符无重复），right 指针每移动到一位，就循环检测 [left , right) 无重复字符区间是否存在与 right指向的字符相同的字符，如果存在就更新 left 指针，将 left移动到区间中与right指向相同字符的下一个位置，继续维护一个无重复的字符区间，同时更新最长子串的长度max。不存在则更新最长子串的长度max，同时继续将 right 往下移动。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0, left = 0, right = 0; 
        if(s.length() == 1)
            max = 1;
        else if( !s.equals("") ){
            //char[] str = s.toCharArray();
            for(right = 1; right < s.length(); right ++){     
                for(int i = left; i < right; i ++){
                    if(s.charAt(i) == s.charAt(right)){
                        // 更新 max 
                        max = right - left > max ? right - left : max;
                        left = i + 1;
                        break;
                    }
                }
                // 更新 max
                max = right- left + 1 > max ? right - left + 1: max;
            }
        }
        return max;
    }
}