本文由作者三汪首發(fā)于簡書。
歷史解題記錄已同步更新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ù)字符的最大子字符串的長度。

代碼和思路

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

A.原始版本

看到這個題目的時候，我是把它當(dāng)成字符串處理題來做的。
沒注意看題目要求返回的是符合要求的最大子字符串長度。
因此第一個版本做了很多字符處理，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;
    }

思路分析：

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

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

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

不足之處：

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

B.改進(jìn)版本

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

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

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

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

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