【滑動(dòng)窗口】字符串的最長(zhǎng)無(wú)重復(fù)子串

1.滑動(dòng)窗口

滑動(dòng)窗口是一個(gè)很實(shí)用的算法(思想)充易,關(guān)于字符串類型的許多題都可以用這個(gè)算法來(lái)解決。
今天找到一個(gè)用來(lái)解釋滑動(dòng)窗口算法的很直觀的例子:轉(zhuǎn)載鏈接
原文作者給出了一個(gè)很形象的類比:卷尺
滑動(dòng)窗口中的這個(gè)“窗口”指的就是卷尺伸出來(lái)的部分,窗口的的頭對(duì)應(yīng)卷尺的頭,窗口的尾就是卷尺伸出來(lái)部分的末尾盏檐,“滑動(dòng)窗口”就是卷尺在一個(gè)給定字符串上移動(dòng)伸縮的過(guò)程。

u=251541792,719776112&fm=26&gp=0.jpg

2. 應(yīng)用

1. 無(wú)重復(fù)字符的最長(zhǎng)子串

問題描述:給定一個(gè)字符串驶悟,請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度胡野。

示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc",所以其長(zhǎng)度為 3痕鳍。

示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "b"给涕,所以其長(zhǎng)度為 1。

示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "wke"额获,所以其長(zhǎng)度為 3够庙。
請(qǐng)注意,你的答案必須是子串的長(zhǎng)度抄邀,"pwke" 是一個(gè)子序列耘眨,不是子串。

問題分析:轉(zhuǎn)載鏈接(有在原文基礎(chǔ)上改動(dòng))

一個(gè)字符串境肾,要在里面找出最長(zhǎng)且沒有重復(fù)字符的子串剔难,就像拿著卷尺在上面不停地移動(dòng)、伸縮測(cè)量奥喻。
子串就是這個(gè)卷尺的伸出部分偶宫,即一個(gè)窗口,左邊縮進(jìn)环鲤,右邊拉出纯趋。
因?yàn)椴荒苡兄貜?fù)的字符,在右端逐漸拉長(zhǎng)的過(guò)程中冷离,每新增加的一個(gè)新字符都要拿來(lái)和左側(cè)子串中的所有字符做對(duì)比吵冒。
在下面的程序里,用 left 指向卷尺頭部西剥,用 right 指向卷尺尾部痹栖,k 則作為子串中字符的索引。
每次對(duì)比開始時(shí)瞭空,用 left 的值初始化 k(即從當(dāng)前窗口左側(cè)第一個(gè)字符開始對(duì)比)揪阿,如發(fā)現(xiàn)重復(fù)字符疗我,就將 k + 1的值賦給 left,即直接將窗口的左側(cè)移動(dòng)到現(xiàn)在窗口中重復(fù)字符的下一個(gè)字符位置南捂。
窗口右側(cè)每次向右滑動(dòng)一格碍粥,如果窗口中子串包含窗口右側(cè)下一個(gè)字符,左側(cè)滑動(dòng)一格或多格黑毅。
與枚舉法相比嚼摩,由于利用了子串中重復(fù)字符的位置,直接將窗口左側(cè)跳到該字符的下一個(gè)位置矿瘦,每次檢查出重復(fù)減少了 k - left 個(gè)子串的自檢枕面。

代碼實(shí)現(xiàn)(Python):

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        left = 0   #窗口左端
        right = 0  #窗口右端
        windowLengh = 0   #窗口長(zhǎng)度
        maxLength = 0   #最長(zhǎng)無(wú)重復(fù)子串長(zhǎng)度
        length = len(s)

        if(length == 0):
            return 0
        for right in range(0, length):
            if(length-left < maxLength):
                return maxLength        #如果窗口左端到字符串末尾的總長(zhǎng)度小于現(xiàn)在的最長(zhǎng)無(wú)重復(fù)子串長(zhǎng)度,那么就無(wú)需繼續(xù)比較了
            windowLengh +=1
            if(right == length-1):  ##達(dá)到最右端
                break
            for k in range(left, right+1):  #從窗口左端開始比較
                if(s[k] == s[right+1]):   #如果重復(fù)
                    if(windowLengh > maxLength):  #如果窗口長(zhǎng)度大于目前最長(zhǎng)無(wú)重復(fù)子串長(zhǎng)度
                        maxLength = windowLengh   #更新最長(zhǎng)無(wú)重復(fù)字符串長(zhǎng)度
                    left = k+1   #移動(dòng)窗口左端
                    windowLengh = right - left + 1  #重新計(jì)算窗口長(zhǎng)度
                    break
        if(windowLengh > maxLength):
            return windowLengh
        else:
            return maxLength

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末缚去,一起剝皮案震驚了整個(gè)濱河市潮秘,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌易结,老刑警劉巖枕荞,帶你破解...
    沈念sama閱讀 212,884評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異搞动,居然都是意外死亡躏精,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,755評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門鹦肿,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)矗烛,“玉大人,你說(shuō)我怎么就攤上這事箩溃〔t吃!?“怎么了?”我有些...
    開封第一講書人閱讀 158,369評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵涣旨,是天一觀的道長(zhǎng)歪架。 經(jīng)常有香客問我,道長(zhǎng)霹陡,這世上最難降的妖魔是什么和蚪? 我笑而不...
    開封第一講書人閱讀 56,799評(píng)論 1 285
  • 正文 為了忘掉前任,我火速辦了婚禮穆律,結(jié)果婚禮上惠呼,老公的妹妹穿的比我還像新娘。我一直安慰自己峦耘,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,910評(píng)論 6 386
  • 文/花漫 我一把揭開白布旅薄。 她就那樣靜靜地躺著辅髓,像睡著了一般泣崩。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上洛口,一...
    開封第一講書人閱讀 50,096評(píng)論 1 291
  • 那天矫付,我揣著相機(jī)與錄音,去河邊找鬼第焰。 笑死买优,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的挺举。 我是一名探鬼主播杀赢,決...
    沈念sama閱讀 39,159評(píng)論 3 411
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼湘纵!你這毒婦竟也來(lái)了脂崔?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,917評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤梧喷,失蹤者是張志新(化名)和其女友劉穎砌左,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體铺敌,經(jīng)...
    沈念sama閱讀 44,360評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡汇歹,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,673評(píng)論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了偿凭。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片秤朗。...
    茶點(diǎn)故事閱讀 38,814評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖笔喉,靈堂內(nèi)的尸體忽然破棺而出取视,到底是詐尸還是另有隱情,我是刑警寧澤常挚,帶...
    沈念sama閱讀 34,509評(píng)論 4 334
  • 正文 年R本政府宣布作谭,位于F島的核電站,受9級(jí)特大地震影響奄毡,放射性物質(zhì)發(fā)生泄漏折欠。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,156評(píng)論 3 317
  • 文/蒙蒙 一吼过、第九天 我趴在偏房一處隱蔽的房頂上張望锐秦。 院中可真熱鬧,春花似錦盗忱、人聲如沸酱床。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,882評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)扇谣。三九已至昧捷,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間罐寨,已是汗流浹背靡挥。 一陣腳步聲響...
    開封第一講書人閱讀 32,123評(píng)論 1 267
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留鸯绿,地道東北人跋破。 一個(gè)月前我還...
    沈念sama閱讀 46,641評(píng)論 2 362
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像瓶蝴,于是被迫代替她去往敵國(guó)和親毒返。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,728評(píng)論 2 351