題目描述
給定一個字符串，找出不含有重複字符的最長子串的長度。
示例：
給定 "abcabcbb" ，沒有重複字符的最長子串是 "abc" ，那麼長度就是 3；
給定 "bbbbb" ，最長的子串就是 "b" ，則長度是 1；
給定 "pwwkew" ，最長子串是 "wke" ，則其長度是 3。
請注意答案必須是一個子串，"pwke" 是子序列，而不是子串。
問題分析
本題是一個字符串處理問題，首先我們明確知道問題的求解是最長不重複子串長度，最長不重複子串可能有多個，如上面示例3，而最長不重複子串長度只有一個唯一的值。本題如果通過暴力求解很容易做出，但是時間複雜度比較高，下面我們將從多個角度一一分析。
解決思路一
使用暴力求解法，通過兩層循環，內層循環統計從當前字符開始最長不重複子串長度，外層循環比較從不同字符開始最長子串長度，保存最大的長度。
代碼實現：
複雜度分析：
時間複雜度：上面使用了兩層循環，複雜度達到O(n2),而每次判斷子串是否為重複串的複雜度為O(n)，因此算法的時間複雜度為O(n3)。
空間複雜度：在判斷子串是否為重複串的時候使用了輔助集合hash_set，它的容量最大為字符串長度或26（英文字母數）的最小值，因此空間複雜度為O(min(n,26))。
算法優化：
上面的算法時間複雜度比較高，但是在此基礎上可以稍微優化一些，我們可以在程序中增加兩個條件判斷語句可以提前結束循環：
當前搜索字符到字符串結尾長度小於等於當前以獲取最大長度maxLen時，這時候maxLen即為算法的結果，可以直接返回結果，如上面第四輪後面長度為3
當內層循環已經檢索到字符串尾部時，證明最長無重複子串已經獲取，可以直接返回結果，如上面第四輪紅色箭頭訪問到字符串結尾時，本次循環結束後則可直接返回。
解決思路二
上面的算法每一輪只移動一個字符，是不是要挨個字符作為子串首字符一一判斷呢？我們看下面情況，當在位置5出現重複字符x時，我們在重複字符x（位置2）之前搜索仍然會在位置5處重複，因此我們可以把上一個重複字母的index+1(即圖中的3)作為新的搜索位置，這樣我們每次只需改變新的開始索引位置（即圖中橘黃色箭頭），而當前搜索位置（即圖中綠色箭頭）不用變，繼續往下搜索，因此效率大大提升。
複雜度分析
時間複雜度：上面只使用了一層循環，因此時間複雜度為O(n)。
空間複雜度：上面使用了一個輔助數組記錄字符上一次出現的位置，大小固定為26，因此空間複雜度為O(1)。
閱讀更多 領釦網 的文章
