[[421659]]

大家好，我是梁唐。

今天給大家聊一個(gè)非常經(jīng)典也非常簡(jiǎn)單的算法，學(xué)會(huì)了這個(gè)算法不說(shuō)能夠縱橫leetcode，但可以解決非常多的問題。并且很多其他的算法也用到了類似的思想，非常有借鑒意義。

這個(gè)算法的名字叫做兩指針?biāo)惴ǎ⑽拿莟wo pointers。

算法原理

既然算法叫做two pointers，那么顧名思義必然和兩個(gè)指針有關(guān)。

首先聲明一點(diǎn)，這里的指針并不是傳統(tǒng)意義上的指針，可以理解成記錄位置的變量或者是標(biāo)記的意思。我們用兩個(gè)變量記錄一個(gè)線性表中的兩個(gè)位置，維護(hù)這兩個(gè)位置圍成的區(qū)間。比如一個(gè)區(qū)間左側(cè)的變量叫l(wèi)，右側(cè)的變量叫r，那么我們維護(hù)的就是[l, r]這個(gè)區(qū)間。

所以兩個(gè)指針的目的是為了維護(hù)區(qū)間，這也是這個(gè)算法的核心目的。所以這個(gè)算法一般的應(yīng)用場(chǎng)景就是尋找一個(gè)合法的最大區(qū)間的問題。當(dāng)然實(shí)際的問題不會(huì)這么直白地告訴你我要求的是一個(gè)合法的區(qū)間，而是會(huì)做各種包裝，玩各種花樣，給你一些彎彎繞，需要你自己通過分析和理解get到題目的核心訴求。

理解了算法的核心目的之后，再來(lái)理解它的原理就容易多了，就只有一個(gè)問題需要解決，就是怎么樣維護(hù)區(qū)間?

我們假設(shè)現(xiàn)在的l和r都停留在了一個(gè)合法的位置，我們把[l, r]理解成一個(gè)區(qū)間，那么l和r的變化都可以看成是區(qū)間的移動(dòng)。

比如，l增大，就可以看成是區(qū)間的左側(cè)在縮小。我們從[l, r]變成[l+1, r]，意味著區(qū)間的左側(cè)彈出了一個(gè)元素。反過來(lái)，如果r增大，則意味著區(qū)間的右側(cè)再拓展，從[l, r]變成[l, r+1]，意味著區(qū)間的右側(cè)添加了一個(gè)新元素。所以我們控制l和r的增大，就相當(dāng)于控制了區(qū)間添加和刪除元素。

當(dāng)我們要移動(dòng)的時(shí)候，我們可以固定將r增大一位，也就是給區(qū)間添加一個(gè)元素。既然添加了新元素，就有可能導(dǎo)致區(qū)間的合法性被破壞。我們就需要做些什么來(lái)維護(hù)區(qū)間的合法性，比如我們可以移動(dòng)左側(cè)的l，讓區(qū)間彈出元素，直到恢復(fù)合法性為止。

隨著r一位一位地移動(dòng)，我們就自然地遍歷了所有合法的區(qū)間，想要找到其他最大或者最小的一個(gè)也就非常簡(jiǎn)單了。

可能光這么看文字會(huì)有些抽象，沒關(guān)系，我們來(lái)看一道具體的例題，來(lái)套用一下剛學(xué)的這個(gè)算法。

例題

我們以leetcode第三題舉例，這題當(dāng)中需要我們?cè)谝粋€(gè)字符串當(dāng)中找到一個(gè)最長(zhǎng)的不包含重復(fù)字符的子串。

表面上來(lái)看這是一道字符串問題，很多人思考的角度估計(jì)都會(huì)圍繞字符串展開。但實(shí)際上，我們只需要把尋找的子串看成是原字符串上的一段區(qū)間，那么這就是一個(gè)尋找最大合法區(qū)間的問題。

在這個(gè)問題當(dāng)中，合法性指的是區(qū)間內(nèi)的字符各不相同。

其實(shí)已經(jīng)很明顯了，我們只要套入一下two pointers算法就行了。首先，我們初始化一個(gè)合法區(qū)間，在這道題當(dāng)中，很容易想到合法區(qū)間可以是[0, 0]。之后的每一步，我們都將r向右移動(dòng)一位，也就是在區(qū)間里插入一個(gè)新字符。由于新字符的插入可能會(huì)引起區(qū)間的合法性遭到破壞，也就是使得某個(gè)字符重復(fù)了。

在這種情況下，我們就移動(dòng)l指針，彈出區(qū)間內(nèi)的元素，直到區(qū)間恢復(fù)合法性為止。為了判斷區(qū)間的合法性是否回復(fù)，我們需要使用一個(gè)map來(lái)存儲(chǔ)區(qū)間內(nèi)每個(gè)元素的個(gè)數(shù)。當(dāng)新插入的字符數(shù)量大于1的時(shí)候，說(shuō)明合法性遭到了破壞，直到數(shù)量恢復(fù)成1為止。

代碼

光看描述可能還有一些抽象，沒關(guān)系，我們?cè)賮?lái)結(jié)合一下代碼進(jìn)行說(shuō)明。

class Solution { 
public: 
    int lengthOfLongestSubstring(string s) { 
        map<char, int> mp; 
        if (s.size() == 0) return 0; 
        int ret = 1; 
        int l = 0; 
        mp[s[0]] = 1; 
        // 每次將r移動(dòng)一位，插入元素 
        for (int r = 1; r < s.size(); r++) { 
            char c = s[r]; 
            // 將s[r]插入map 
            if (mp.count(c)) mp[c]++; 
            else mp[c] = 1; 
            // 如果map中s[r]的數(shù)量大于1，說(shuō)明引起沖突 
            // 彈出左側(cè)元素，直到合法性恢復(fù) 
            while (mp[c] > 1) { 
                mp[s[l++]]--; 
            } 
            ret = max(r - l + 1, ret); 
        } 
        return ret; 
    } 
}; 

結(jié)合一下代碼注釋，整體邏輯還是比較清晰的。

就是一個(gè)右側(cè)拓展，左側(cè)收縮的過程，比較容易疑惑的點(diǎn)是為什么這樣能找到最大的區(qū)間?其實(shí)這里面還蘊(yùn)藏著貪心法的思想，只不過比較難想到。

可以用數(shù)學(xué)歸納法簡(jiǎn)單地進(jìn)行一個(gè)證明，首先，很明顯[0, 0]是以0為右端點(diǎn)能夠找到的最大合法區(qū)間。

我們假設(shè)[l, r]是以r為右邊界能夠找到的最大合法區(qū)間，也就是說(shuō)l是它能延伸到的最左側(cè)的位置。那么當(dāng)我們將r移動(dòng)到r+1，以r+1為右側(cè)邊界，往左側(cè)去尋找最大合法區(qū)間，找到的左側(cè)邊界，我們叫做l'。請(qǐng)問這個(gè)l'可能小于l嗎?

很顯然，不可能，因?yàn)槿绻鹟' < l，那么[l', r]必然也是合法的，就和我們假設(shè)的前提矛盾了。所以l'一定是大于等于l的。這就證明了，我們通過這樣的遞推算法找到的區(qū)間都是基于右側(cè)端點(diǎn)的最大合法區(qū)間，我們基于每一個(gè)可能構(gòu)成右側(cè)端點(diǎn)的位置都尋找了最大合法區(qū)間，全局最大合法區(qū)間也必然在其中。

優(yōu)化

如果能夠?qū)懗龌蛘呃斫馍厦娴拇a，那么對(duì)于two pointers算法的理解就算是勉強(qiáng)過關(guān)了，不過還沒有結(jié)束。

因?yàn)槿绻麑?duì)于它理解足夠深入，就會(huì)發(fā)現(xiàn)這道題還有繼續(xù)優(yōu)化的空間，繼續(xù)優(yōu)化的前提依賴我們對(duì)算法的理解。

那么哪里還可以優(yōu)化呢?其實(shí)很簡(jiǎn)單，我用紅框標(biāo)記一下就知道了。

我們?cè)诰S護(hù)區(qū)間合法性的時(shí)候，使用了while循環(huán)彈出左側(cè)的邊界。仔細(xì)想，我們使用while循環(huán)的目的是什么?是移動(dòng)區(qū)間的左側(cè)邊界l，移動(dòng)l的目的是什么?是為了維護(hù)區(qū)間合法性，那維護(hù)區(qū)間合法性的核心在哪里?在于彈出那個(gè)和s[r]相同的字符。

重點(diǎn)來(lái)了，為了彈出和s[r]相同的字符。我們可以想到什么?既然本質(zhì)目的是為了彈出這個(gè)引起沖突的字符，除了一位一位地移動(dòng)，還有沒有其他辦法?我們既然已經(jīng)用map了，使用一下map記錄一下每個(gè)字符的位置行不行?完全可以!這樣的話，我們就把循環(huán)的若干次執(zhí)行替換成了一次查找，大大加快了速度。

如果再機(jī)靈一點(diǎn)，又可以想到，我們其實(shí)也沒有必要使用map，因?yàn)槲覀冇涗浀氖亲址奈恢谩Ｗ址腶scii碼范圍很小，我們完全可以用數(shù)組來(lái)存儲(chǔ)，這樣的話查找會(huì)更快，只有。

我們來(lái)看優(yōu)化之后的代碼：

class Solution { 
public: 
    int lengthOfLongestSubstring(string s) { 
        int mp[128]; 
        memset(mp, -1, sizeof mp); 
        if (s.size() == 0) return 0; 
        int ret = 1; 
        int tmp = 0; 
        int l = 0; 
        mp[s[0]] = 0; 
        int n = s.size(); 
        for (int r = 1; r < n; r++) { 
            char c = s[r]; 
            if (mp[c] >= l) l = mp[c]+1; 
            mp[c] = r; 
            ret = max(r - l + 1, ret); 
        } 
        return ret; 
    } 
}; 

我們重點(diǎn)看下這個(gè)部分：

如果最近的一個(gè)s[r]在l的右側(cè)，說(shuō)明會(huì)構(gòu)成沖突，那么我們直接把l移動(dòng)到它的后一位即可，就代替了while循環(huán)一位一位移動(dòng)l的操作，大大提升了運(yùn)行速度。

實(shí)際上也的確如此，優(yōu)化之前用了36ms，而優(yōu)化之后只用了12ms，足足快了三倍。

這道例題非常經(jīng)典，既有two pointers的應(yīng)用，還可以基于它的理解進(jìn)行進(jìn)一步地優(yōu)化，能把這道題吃透，就足夠領(lǐng)會(huì)算法的精髓，并且它的難度還不是非常大，對(duì)新手足夠友好。

如果之前沒學(xué)過two pointers算法的話，可以多琢磨一下這道題，一定會(huì)有很大的收獲。