算法基礎（六）| 雙指針算法及模闆應用

⭐寫在前面的話：本系列文章旨在複習算法刷題中常用的基礎算法與資料結構，配以詳細的圖例解釋，總結相應的代碼模闆，同時結合例題以達到最佳的學習效果。本專欄面向算法零基礎但有一定的C++基礎的學習者。若C++基礎不牢固，可參考：​​10min快速回顧C++文法​​，進行文法複習。

🔥本文已收錄于算法基礎系列專欄： ​​算法基礎教程​​ 免費訂閱，持續更新。

雙指針算法

雙指針算法的常見情況：

• 雙指針在兩個數組上（例如歸并排序等等）



• 雙指針在一個數組上

常見通用代碼模闆

for(i = 0, j =0; i < n; i++ )
{
    while(j < i && check(i,j))j++;
    //再加上每道題目的具體邏輯
}      

雙指針的核心思想是優化。

常見的周遊一共是雙重循環，複雜度是O()

但是雙指針算法雖然是看起來是雙重循環，但是實際上每個指針移動的次數是不超過O(n)的，兩個指針的總次數不超過O(2n)。将之前的樸素算法優化到O(n)。

舉例：分行輸出字元串

假設有一個字元串“acb def jhi”以空格分開，現在要将其以空格為分解，換行輸出。

基本思路：采用雙指針算法

首先i和j在同一起點位置，然後j進行掃描。

j停在空格分界的位置上，輸出兩位置之間的字元串

把指針i移動在j上。

模闆應用

#include <iostream>
#include <string.h>

using namespace std;

int main()
{
    char str[1000];
    
    gets(str);
    
    int n = strlen(str);
    
    for(int i = 0; i< n; i++)
    {
        int j = i;
        while(j < n && str[j] != ' ')j ++;
        
        //具體邏輯
        for(int k = i; k < j;k++)cout << str[k];
        
        i = j;
    }
    return 0;
}      

最長連續不重複子序列

給定一個長度為 nn 的整數序列，請找出最長的不包含重複的數的連續區間，輸出它的長度。

輸入格式

第一行包含整數 nn。

第二行包含 nn 個整數（均在 0∼1050∼105 範圍内），表示整數序列。

輸出格式

共一行，包含一個整數，表示最長的不包含重複的數的連續區間的長度。

資料範圍

1≤n≤1051≤n≤105

輸入樣例：

5
1 2 2 3 5      

輸出樣例：

3      

樸素做法：

for(int i = 0; i < n; i ++)
{
  for(int j = 0; j < i; j++)
       if(chack(i,j))
       {
           res = max(res, i - j +1);
       }
}      

雙指針算法模闆：

for(int i = 0; i < n; i++)
{
    while(j <= i && check(j,i))j ++;
    res = max(res, i - j + 1);
}      

雙指針基本思路：

首先i循環周遊，j的含義是j最遠能到什麼地方，因為需要計算的是無重複的個數，是以j和i之間無重複的數。

可以證明：在i不斷後移同時，j必然也是單調後移的，不可能出現j前移的情況，因為j如果前移，那麼就證明剛剛最大的位置并非最優值，這與剛剛的結論沖突。

有了單調這一層性質，就可以采用雙指針這種單調隊列的思想優化。因為可以使j在i周遊的時候仍然記錄上次的位置。

具體條件的應用；

• 開辟一個動态數組來記錄每個值出現多少次。例如原來需要判斷的數組為a[n]。記錄時就可以另外開辟以該值為序列号的數組S[N];

• i往後移動一格，代表有一個數進來了，即S[a[i]]++;
• j往後移動一格，代表有一個數出去了，即S[a[j]]--;

這樣可以動态地統計區間内有多少個數。

• 其中如果有重複的值，一定是新加進來的a[i]，那麼那個值統計後，該記錄數組的值大于1，那麼j下次就必須去掉那個值，移動到該值之後。

for(int i = 0; i < n; i++)
{
    while(S[a[i]] > 1)XXX;
    res = max(res, i - j + 1);
}      

代碼

#include <iostream>

using namespace std;

const int N = 100010;

int S[N],a[N];
int n;


int main()
{
    cin >> n;
    for(int i = 0; i< n; i++)cin >> a[i];
    
    int res = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
        S[a[i]]++;
        while(S[a[i]] > 1)
        {
            //當停止時，說明和i相同的值已經被删了，即j停在了重複值之後
            S[a[j]] --;
            j ++;
        }
        
        res = max(res, i - j + 1);
    }
    cout << res;
    return 0;
}