[LeetCode] 3. Longest Substring Without Repeating Characters 題解
輸入一個字串，找到其中最長的不重複子串
例1：
輸入："abcabcbb" 輸出：3 解釋：最長非重複子串為"abc" 複製程式碼
例2：
輸入："bbbbb" 輸出：1 解釋：最長非重複子串為"b" 複製程式碼
例3：
輸入："pwwkew" 輸出：3 解釋：最長非重複子串為"wke" 複製程式碼
問題難度
Medium
解題思路
本題採用「滑動視窗法」可以達到較理想的時間複雜度 O(n)，滑動視窗指的是當前非重複子串所在的視窗，此滑動視窗有兩種操作方法
- 檢查下一個字元是否會重複，如未重複，則將視窗向右擴大
- 發現重複字元，則將視窗右邊界保持不變，左邊界右移，以此縮小視窗
上面的操作比較容易理解，唯一需要注意的是第 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 = 0 current_substring = [None]*128 current_substring_len = 0 begin_index = 0 for 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_len current_substring_len += 1 else: if maxlen < current_substring_len: maxlen = current_substring_len sub_len = current_substring[stoi] - begin_index + 1 begin_index = current_substring[stoi] + 1 current_substring_len -= sub_len current_substring[stoi] = current_substring_len + begin_index current_substring_len += 1 if maxlen < current_substring_len: maxlen = current_substring_len return maxlen 複製程式碼
以上程式碼中，current_substring
是一個緩衝區，用來存放當前子字串，緩衝區宣告為 128 個是為了讓陣列的下標空間能容納 128 個 ASCII 字元，即這裡用陣列的下標來表示字元，這樣做的好處是可以很快的知道某個字元是否出現重複，陣列的內容我們填的是該字元對應的下標，例如字串"abcde"
填到current_substring
中為：
index:0..979899100 101 .. +---+---+---+---+---+---+---+ current_substring: |...| 0 | 1 | 2 | 3 | 4 |...| +---+---+---+---+---+---+---+ 複製程式碼
我們用變數begin_index
來記錄當前視窗在字串中的起始位置，而current_substring_len
用來記錄當前視窗的長度。for
迴圈是對字串的遍歷。
首先將字元轉化為其對應的整數stoi
，檢查stoi
中的內容是否為空，或其儲存的位置是否在視窗的左邊，如是則表示該字元在begin_index
之後未出現過，非重複子串可以繼續累加。
否則表示出現重複，出現重複時，需要將視窗的左邊界右移，或者說對新的滑動視窗進行初始化，實際上只需更新begin_index
和current_substring_len
兩個值。
最後，我們需要在每一次視窗改變時，或在結束遍歷時，判斷當前子字串的長度是否是最長的，並將最長串儲存在maxlen
中，作為結果返回。