Longest Substring Without Repeating Characters

找出一串字符中的最长不重复子串，并输出长度

input

[b,a,c,d,e,f,a]

output

6

开始的复杂度是o2(n)，最后一组数据超时了。

    public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() < 2){
                return s.length();
        }
        String result = "";
        String temp = "";
        for(int i = 0; i < s.length(); i++){
            temp = "" + s.charAt(i); // 进行下一个赋值
            for(int j = i+1; j < s.length(); j++){
                if(!temp.contains(""+s.charAt(j))){
                    temp += s.charAt(j);
                    if(temp.length() > result.length()){
                        result = temp;
                    }
                }else{
                    if(temp.length() > result.length()){
                        result = temp;
                    }
                    temp= "";
                    break;
                }
            }
        }

        return result.length();    
    }
}

看了题解，其实可以记录状态。就是说，当abcdefa的检测到重复时，因为abcdef已经检测过了，不用重头从bcdef检测，而是直接检测bcdefa这个长度的字符是否和前面重复即可。用2个变量i,j，从头开始遍历检测，当检测到重复的时候，直接i,j各向右位移一位。同时，因为所有字符是可以枚举的，可以用一个数组记录状态是否被检查过。

修改过的代码：

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        boolean[] visited = new boolean[256];
        int i = 0, j = 0;
        int max = 0, cur = 0;
        while(i < s.length()){
            if(!visited[s.charAt(i)]){
                visited[s.charAt(i)] = true;
                i++;
            }else{
                while(s.charAt(j)!=s.charAt(i)){
                    visited[s.charAt(j)] = false;
                    j++;
                }
                i++;
                j++;
            }
            cur = i - j;
            max = max > cur ?max:cur;
        }
        return max;  
    }
}

题外话……发布的时候趁机做题，结果没有好好验日志，线上报了一堆error……幸好老大没发现……