問題描述

輸入一個字符串，找到其中最長的不重復子串

例1：

輸入："abcabcbb"
輸出：3
解釋：最長非重復子串為"abc"
復制代碼

例2：

輸入："bbbbb"
輸出：1
解釋：最長非重復子串為"b"
復制代碼

例3：

輸入："pwwkew"
輸出：3
解釋：最長非重復子串為"wke"
復制代碼

問題難度

Medium

解題思路

本題采用「滑動窗口法」可以達到較理想的時間復雜度 O(n)，滑動窗口指的是當前非重復子串所在的窗口，此滑動窗口有兩種操作方法

1. 檢查下一個字符是否會重復，如未重復，則將窗口向右擴大
2. 發現重復字符，則將窗口右邊界保持不變，左邊界右移，以此縮小窗口

上面的操作比較容易理解，唯一需要注意的是第 2 點中，當發現重復字符時，窗口左邊界向右移動幾個單位，我們可以看一個示意圖：

+---------+ 
| a b c d | e d x y z 
+---------++-----------+ 
| a b c d e | d x y z // 未發現重復，向右擴大窗口
+-----------++-----+ 
a b c d | e d | x y z // 發現重復，縮小窗口+-----+
復制代碼

假設輸入字符串為 "abcdedxyz"，一直到我們遍歷到字符 e 時，均未發現重復的字符串，至此對窗口進行的操作都是向右擴大，當檢查到下一個字符 d 時，由于前面字符串中已經出現過該字符，所以窗口左邊界需要進行右移，移動的位置、即新子串窗口的起始點，正好是兩個重復字符中、第一個重復字符的右邊，如圖所示為字符 e 所在的位置。

至此，我們可以開始寫程序了：

def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""maxlen = 0current_substring = [None]*128current_substring_len = 0begin_index = 0for i in s:stoi = ord(i)if current_substring[stoi] is None or current_substring[stoi] < begin_index:current_substring[stoi] = begin_index + current_substring_lencurrent_substring_len += 1else:if maxlen < current_substring_len:maxlen = current_substring_len sub_len = current_substring[stoi] - begin_index + 1begin_index = current_substring[stoi] + 1current_substring_len -= sub_lencurrent_substring[stoi] = current_substring_len + begin_indexcurrent_substring_len += 1if maxlen < current_substring_len:maxlen = current_substring_lenreturn maxlen
復制代碼

以上代碼中，current_substring 是一個緩沖區，用來存放當前子字符串，緩沖區聲明為 128 個是為了讓數組的下標空間能容納 128 個 ASCII 字符，即這里用數組的下標來表示字符，這樣做的好處是可以很快的知道某個字符是否出現重復，數組的內容我們填的是該字符對應的下標，例如字符串 "abcde" 填到 current_substring 中為：

            index:   0..97  98  99  100 101 ..+---+---+---+---+---+---+---+
current_substring: |...| 0 | 1 | 2 | 3 | 4 |...|+---+---+---+---+---+---+---+
復制代碼

我們用變量 begin_index 來記錄當前窗口在字符串中的起始位置，而 current_substring_len 用來記錄當前窗口的長度。for 循環是對字符串的遍歷。

首先將字符轉化為其對應的整數 stoi，檢查 stoi 中的內容是否為空，或其存儲的位置是否在窗口的左邊，如是則表示該字符在 begin_index 之后未出現過，非重復子串可以繼續累加。

否則表示出現重復，出現重復時，需要將窗口的左邊界右移，或者說對新的滑動窗口進行初始化，實際上只需更新 begin_index 和 current_substring_len 兩個值。

最后，我們需要在每一次窗口改變時，或在結束遍歷時，判斷當前子字符串的長度是否是最長的，并將最長串存儲在 maxlen 中，作為結果返回。

原題鏈接