[[421659]]

大家好，我是梁唐。

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

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

算法原理

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

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

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

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

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

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

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

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

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

例題

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

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

在這個問題當中，合法性指的是區間內的字符各不相同。

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

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

代碼

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

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]的數量大于1，說明引起沖突 
            // 彈出左側元素，直到合法性恢復 
            while (mp[c] > 1) { 
                mp[s[l++]]--; 
            } 
            ret = max(r - l + 1, ret); 
        } 
        return ret; 
    } 
}; 

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

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

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

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

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

優化

如果能夠寫出或者理解上面的代碼，那么對于two pointers算法的理解就算是勉強過關了，不過還沒有結束。

因為如果對于它理解足夠深入，就會發現這道題還有繼續優化的空間，繼續優化的前提依賴我們對算法的理解。

那么哪里還可以優化呢?其實很簡單，我用紅框標記一下就知道了。

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

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

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

我們來看優化之后的代碼：

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的右側，說明會構成沖突，那么我們直接把l移動到它的后一位即可，就代替了while循環一位一位移動l的操作，大大提升了運行速度。

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

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

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