本文由作者三汪首發(fā)于簡(jiǎn)書。
歷史解題記錄已同步更新github.

改進(jìn)版solution提交結(jié)果.png

題目

Problem Description:
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.

題目分析

題意是讓我們返回給定字符串不含重復(fù)字符的最大子字符串的長(zhǎng)度。

代碼和思路

我會(huì)對(duì)自己的原始提交版本做個(gè)記錄。
沒耐心看的同學(xué)可以跳過原始版本直接去看后面的B和C，
分別是我對(duì)當(dāng)前Java solution最優(yōu)解的分析和我自己的改進(jìn)版本。

A.原始版本

看到這個(gè)題目的時(shí)候，我是把它當(dāng)成字符串處理題來(lái)做的。
沒注意看題目要求返回的是符合要求的最大子字符串長(zhǎng)度。
因此第一個(gè)版本做了很多字符處理，Runtime也很感人，用了90ms,排位在12.61%的位置。

1.0版本代碼如下：

    private int lengthOfLongestSubstring_1_0(String str){
        if (str==null || str.equals("")) {
            return 0;
        }
        String[] subs = new String[str.length()];
        int subsIndex = 0;
        String[] chars = str.split("");
        StringBuffer sb = new StringBuffer(chars[0]);
        for (int i = 1; i < chars.length; i++) {
            if (!sb.toString().contains(chars[i])) {
                sb.append(chars[i]);
            }else if(sb.indexOf(chars[i]) != sb.length()-1){
                subs[subsIndex++] = sb.toString();
                sb.delete(0,sb.indexOf(chars[i])+1);
                sb.append(chars[i]);
            }else{
                subs[subsIndex++] = sb.toString();
                sb.delete(0, sb.length());
                sb.append(chars[i]);
            }
        }
        subs[subsIndex++] = sb.toString();
        int maxLength = subs[0].length();
        for (int i = 1; i < subs.length; i++) {
            if (subs[i] == null) {
                return maxLength;
            }
            if (subs[i].length() > maxLength) {
                maxLength = subs[i].length();
            }
        }
        return maxLength;
    }

思路分析：

這段代碼的思路是先把給定字符串分解成單個(gè)字符數(shù)組，再依次寫入StringBuffer。

當(dāng)出現(xiàn)重復(fù)字符時(shí)，根據(jù)重復(fù)字符在字符串中的位置分兩種情況處置。
情況一、重復(fù)字符不是當(dāng)前字符串的最后一個(gè)字符時(shí)：
將當(dāng)前StringBuffer中拼好的字符串寫入String[]數(shù)組，刪除從字符串開端到重復(fù)字符位置的所有字符，從重復(fù)字符的后一個(gè)字符為字符串的開端，繼續(xù)拼接字符串。
情況二、重復(fù)字符是當(dāng)前字符串的最后一個(gè)字符時(shí)：
將當(dāng)前StringBuffer中拼好的字符串寫入String[]數(shù)組，清空StringBuffer,重新開始新的字符串拼接。

最后遍歷String[]數(shù)組，獲取長(zhǎng)度最大的字符串的長(zhǎng)度并返回。

不足之處：

在這個(gè)版本的代碼中我有一個(gè)很大的弊病是我忘了String可以字節(jié)調(diào)用.toCharArray()方法獲取char[]數(shù)組，而是用了.split("")來(lái)把給定字符串分割成一個(gè)個(gè)由單個(gè)字符組成的字符串。

B.改進(jìn)版本

改進(jìn)版本不再使用字符串拼接的方法來(lái)實(shí)現(xiàn)。
而是使用一個(gè)快指針(Runner)和一個(gè)慢指針(Walker)來(lái)遍歷由給定字符串分解的char[]數(shù)組，直接獲取最大子字符串長(zhǎng)度。
這種方式Runtime只有36ms,排位在99.94%的位置。

值得一提的是，這個(gè)改進(jìn)版本是在看了一會(huì)兒會(huì)分析的當(dāng)前Java最優(yōu)解以后結(jié)合自己思考而來(lái)的。
我通過寫自己的改進(jìn)版來(lái)理解最優(yōu)解的代碼思路。這是一個(gè)小心得，你也可以試試。

1.1版本代碼如下：

    private int lengthOfLongestSubstring_1_1(String str){
        //It's my own habit to check if the input is empty.
        if (str == null) {
            return 0;
        }
        char[] chars = str.toCharArray();
        if (chars.length<2) {
            return chars.length;
        }
        int maxLength = 0,spliter = 0;
        for (int i = 1; i < chars.length; i++) {
            for (int j = spliter ; j < i ; j++) {
                if (chars[i]==chars[j]) {
                    int tempLength = i-spliter;
                    maxLength = maxLength > tempLength ? maxLength : tempLength;
                    spliter = j+1;
                    break;
                }
            }
        }
        maxLength = maxLength > chars.length-spliter ? maxLength : chars.length-spliter;
        return maxLength;
    }

思路分析：

1. 當(dāng)給定字符串長(zhǎng)度小于2時(shí)，直接返回它的長(zhǎng)度。
2. 使用快指針和慢指針遍歷給定字符串分解而來(lái)的char[]數(shù)組
   2.1 使用spliter來(lái)記錄重復(fù)字符的下一個(gè)字符的位置（重復(fù)字符和它前面的字符對(duì)新子字符串沒有意義），初始值為0。
   2.2 使用maxLength來(lái)記錄每次遍歷時(shí)子字符串的最大長(zhǎng)度。當(dāng)有新的最大子字符串產(chǎn)生（遇到重復(fù)字符或結(jié)束遍歷）時(shí)，判斷其長(zhǎng)度是否大于maxLength。若是，則更新maxLength。
3. 我不知道我真的解釋清楚了沒，雖然我覺得我解釋清楚了。如果正在看的你哪里不理解，歡迎留言討論：）

C.截至此刻LeetCode上用時(shí)最少的Java Solution

代碼如下：

    /**
     * 
     * <p>
     * Description:The best solution on LeetCode by this time.<br />
     * Runtime:35ms<br />
     * </p>
     * @version 0.1 2017年12月8日
     * @param s
     * @return
     * int
     */
    private int lengthOfLongestSubstring_best(String s) {
        char[] chars = s.toCharArray();
        if(2 > chars.length){
            return chars.length;
        }
        int max = 0;
        int split_at = 0;
        int cur_len = 1;
        for(int i=1;i<chars.length;i++){
            int j = split_at;
            for(;j<i;j++){
                if(chars[i] == chars[j]){
                    break;
                }
            }
            if(j < i){
                split_at = j+1;
                cur_len = i-j;
            }else{
                cur_len++;
            }
            if(cur_len > max) max = cur_len;
        }
        return max;
    }

思路分析：

1. 主體思路同改進(jìn)版本思路，下面來(lái)講一些細(xì)節(jié)方面的不同。
2. 使用cur_len字段來(lái)記錄當(dāng)前子字符串長(zhǎng)度，初始值為1。
   使用split_at字段來(lái)記錄上一次碰到的重復(fù)字符的下一個(gè)字符的位置，初始值為0。
   使用max字段記錄每次遍歷時(shí)子字符串的最大長(zhǎng)度。
3. 當(dāng)出現(xiàn)重復(fù)字符時(shí)，break跳出快指針循環(huán)（即內(nèi)層for循環(huán)，快指針為j）。
   結(jié)束內(nèi)層for循環(huán)以后，判斷快指針與慢指針（慢指針為i）是否相等。
   當(dāng)出現(xiàn)重復(fù)字符時(shí)，快指針與慢指針是不會(huì)相等的。因?yàn)闀?huì)break跳出循環(huán)。
   3.1 若快指針與慢指針相等，則當(dāng)前子字符串沒有遇到重復(fù)字符。cur_len自增。
   3.2 若快指針小于慢指針，則不含重復(fù)字符的當(dāng)前子字符串長(zhǎng)度為cur_len=i-j，更新split_at字段。
   3.3 快指針不可能大于慢指針。因?yàn)閮?nèi)層for循環(huán)條件是j<i。
4. 每次結(jié)束外層循環(huán)時(shí)，判斷cur_len是否大于max。若是，則更新max。
5. 我不知道我真的解釋清楚了沒，雖然我覺得我解釋清楚了。如果正在看的你哪里不理解，歡迎留言討論：）

以上。
希望我的文章對(duì)你能有所幫助。
我不能保證文中所有說法的百分百正確，
但我能保證它們都是我的理解和感悟以及拒絕直接復(fù)制黏貼（確實(shí)需要引用的部分我會(huì)附上源地址）。
有什么意見、見解或疑惑，歡迎留言討論。