[[421659]]

大家好，我是梁唐。

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

這個算法的名字叫做兩指針算法，英文名是two pointers。

算法原理

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

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

所以兩個指針的目的是為了維護區(qū)間，這也是這個算法的核心目的。所以這個算法一般的應(yīng)用場景就是尋找一個合法的最大區(qū)間的問題。當然實際的問題不會這么直白地告訴你我要求的是一個合法的區(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的增大，就相當于控制了區(qū)間添加和刪除元素。

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

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

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

例題

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

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

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

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

在這種情況下，我們就移動l指針，彈出區(qū)間內(nèi)的元素，直到區(qū)間恢復合法性為止。為了判斷區(qū)間的合法性是否回復，我們需要使用一個map來存儲區(qū)間內(nèi)每個元素的個數(shù)。當新插入的字符數(shù)量大于1的時候，說明合法性遭到了破壞，直到數(shù)量恢復成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è)元素，直到合法性恢復 
            while (mp[c] > 1) { 
                mp[s[l++]]--; 
            } 
            ret = max(r - l + 1, ret); 
        } 
        return ret; 
    } 
}; 

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

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

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

我們假設(shè)[l, r]是以r為右邊界能夠找到的最大合法區(qū)間，也就是說l是它能延伸到的最左側(cè)的位置。那么當我們將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)化呢?其實很簡單，我用紅框標記一下就知道了。

我們在維護區(qū)間合法性的時候，使用了while循環(huán)彈出左側(cè)的邊界。仔細想，我們使用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)會算法的精髓，并且它的難度還不是非常大，對新手足夠友好。

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