[[421659]]

大家好，我是梁唐。

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

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

算法原理

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

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

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

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

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

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

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

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

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

例題

我們以leetcode第三題舉例，這題當(dāng)中需要我們在一個字符串當(dāng)中找到一個最長的不包含重復(fù)字符的子串。

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

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

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

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

代碼

光看描述可能還有一些抽象，沒關(guān)系，我們再來結(jié)合一下代碼進行說明。

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移動一位，插入元素 
        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，說明引起沖突 
            // 彈出左側(cè)元素，直到合法性恢復(fù) 
            while (mp[c] > 1) { 
                mp[s[l++]]--; 
            } 
            ret = max(r - l + 1, ret); 
        } 
        return ret; 
    } 
}; 

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

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

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

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

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

優(yōu)化

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

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

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

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

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

如果再機靈一點，又可以想到，我們其實也沒有必要使用map，因為我們記錄的是字符的位置。字符的ascii碼范圍很小，我們完全可以用數(shù)組來存儲，這樣的話查找會更快，只有。

我們來看優(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; 
    } 
}; 

我們重點看下這個部分：

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

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

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

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