問題描述

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

例1：

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

例2：

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

例3：

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

問題難度

Medium

解題思路

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

檢查下一個字符是否會重復(fù)，如未重復(fù)，則將窗口向右擴(kuò)大

發(fā)現(xiàn)重復(fù)字符，則將窗口右邊界保持不變，左邊界右移，以此縮小窗口

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

+---------+ | a b c d | e d x y z +---------++-----------+ | a b c d e | d x y z // 未發(fā)現(xiàn)重復(fù)，向右擴(kuò)大窗口 +-----------++-----+ a b c d | e d | x y z // 發(fā)現(xiàn)重復(fù)，縮小窗口+-----+ 復(fù)制代碼

假設(shè)輸入字符串為 "abcdedxyz"，一直到我們遍歷到字符 e 時，均未發(fā)現(xiàn)重復(fù)的字符串，至此對窗口進(jìn)行的操作都是向右擴(kuò)大，當(dāng)檢查到下一個字符 d 時，由于前面字符串中已經(jīng)出現(xiàn)過該字符，所以窗口左邊界需要進(jìn)行右移，移動的位置、即新子串窗口的起始點(diǎn)，正好是兩個重復(fù)字符中、第一個重復(fù)字符的右邊，如圖所示為字符 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 復(fù)制代碼

以上代碼中，current_substring 是一個緩沖區(qū)，用來存放當(dāng)前子字符串，緩沖區(qū)聲明為 128 個是為了讓數(shù)組的下標(biāo)空間能容納 128 個 ASCII 字符，即這里用數(shù)組的下標(biāo)來表示字符，這樣做的好處是可以很快的知道某個字符是否出現(xiàn)重復(fù)，數(shù)組的內(nèi)容我們填的是該字符對應(yīng)的下標(biāo)，例如字符串 "abcde" 填到 current_substring 中為：

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

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

首先將字符轉(zhuǎn)化為其對應(yīng)的整數(shù) stoi，檢查 stoi 中的內(nèi)容是否為空，或其存儲的位置是否在窗口的左邊，如是則表示該字符在 begin_index 之后未出現(xiàn)過，非重復(fù)子串可以繼續(xù)累加。

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

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

原題鏈接

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的[LeetCode] 3. Longest Substring Without Repeating Characters 题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。