讓我們從一個例題來開始認識雙指標吧！

我們可以先從最暴力最單純的作法出發：我們可以窮舉每一個 $(l, r)$，並計算 $a_l$ 到 $a_r$ 的數字總和，然後看看這個總和有沒有超過 $t$，有的話再來檢查看看有沒有比原本的最小值更小，窮舉完之後我們就得到了我們的答案。

很好，這個作法很單純，用三層的迴圈就可以解決，然而時間複雜度也因此是 $O(N^3)$，因此我們可以再來想想看有沒有更好的作法。

重新檢視我們的流程，我們發現我們好好的處理我們窮舉的順序的話，我們就不用對每組 $(l, r)$ 都重新計算一次區間和了！具體的作法是，我們只要固定 $l$，然後讓 $r$ 逐漸變大，此時因為 $s_{l, r} + a_{r + 1}= s_{l, r+1}$ (這裡的 $s_{l, r}$ 代表 $[l, r]$ 的區間和)，因此我們可以用 $O(N)$ 的時間找出以 $l$ 為左界的所有區間和。針對每個 $l$ 都做一次，總複雜度就優化到了 $O(N^2)$。

太好了，但還是差了一點，我們就來接著看我們還可以再簡化些什麼。

首先，當我們找到一個 $(l, r), s_{l, r} \ge t$ 時，對於所有的 $R > r$，我們都可以確定 $(l, R)$ 不會是我們想找到的答案。原因是，就算 $s_{l, R} > t$，也會因為 $R - l + 1 > r - l + 1$ 而肯定 $(l, R)$ 不會比 $(l, r)$ 來得好。也就是說，在我們找到一組 $(l, r), s_{l, r} \ge t$ 後，我們就無須考慮所有的 $(l, R), R > r$ 是否為答案了。

那就代表說，當我們固定 $l$ 窮舉 $r$ 時，我們只要找到第一個滿足條件的 $r$ 就可以了，因為我們知道更後面的 $r$ 一定不會是答案，這個時候，我們就可以來考慮下一個左界 $l + 1$。此時，我們也可以來看看移動左界時有沒有什麼地方是可以改進的：我們會需要考慮 $(l + 1, r - 1)$ 嗎？答案是不必的，因為如果 $s_{l + 1, r - 1} \ge t$ 的話，$s_{l, r - 1}\ge t$ 也必然是對的，也就是說，在左界為 $l$ 時，我們理當枚舉到 $r-1$ 時就會停下了，根本輪不到 $r$，因此，針對左界 $l + 1$，我們其實可以從 $r$ 繼續我們的枚舉。

這樣的行為看起來就像，我們有左指標與右指標，他們各會指向序列裡的某一格，我們把兩個指標框住的區間作為我們考慮的子序列，他們一開始都會在起點，接下來我們固定左指標、並把右指標一格一格向右移動，當我們發現兩個指標框住的區間和大於 $t$ 時，我們就可以紀錄長度，並固定右指標、將左指標向右移動一格，接下來又開始移動右指標來尋找下一個合法的區間，直到左右指標都抵達終點。

那這樣時間複雜度要怎麼算呢？我們會發現每次移動指標都一定是一格，因此把兩個指標都移到終點一共要移動 $2N$ 次，此外，每次移動時我們更新區間和的花費是 $O(1)$ 的 (加上右邊的新數字或是減去左邊的舊數字)，因此我們的時間複雜度為 $O(N)$。

範例程式碼如下：

int main () {
    int n; // 序列長度
    int t; // 目標大小
    int arr[100000]; // 序列

    cin >> n; // 讀輸入
    cin >> t;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];

    // 左右指標，一開始指向起點，這裡採用左閉右開來實做
    // (包含左界但不包含右界)。
    int l = 0, r = 0;
    int sum = 0; // 子序列和。
    // 最短的合法子序列長度，用很大的數字作為預設值。
    int ret = INT_MAX;

    for (; l < n; ++l) { // 移動左指標。
        // 只要子序列和不夠大而且右指標沒出界的話就移動右
        // 指標。
        while (sum < t && r < n) {
            sum += arr[r];
            r++;
        }
        // 區間和夠大就更新答案。
        if (sum >= t)
            ret = min(ret, r - l);
        // 配合左指標更新子序列和。
        sum -= arr[l];
    }

    cout << (ret == INT_MAX ? 0 : ret) << '\n';

    return 0;
}

接著我們來看看雙指標的另一種使用情境：

這道題目在二分搜尋法的章節中的 3sum 相當類似，我們也確實可以使用當時的作法來做出這道題目，但在這裡我們就思考看看使用上雙指標能不能得出不一樣的作法吧！

先嘗試模仿前面「子序列和」這道題目的作法，讓 $l, r$ 從 $0$ 開始，先枚舉右界直到找到第一個 $a_l + a_r \ge t$ 的臨界點（這裡的 $a_l$ 指的是第 $l$ 的元素，$t$ 則是目標和），如果此時 $(l, r)$ 滿足 $a_l + a_r = t$ 就代表我們找到了答案。

否則，我們就需要來移動左界來尋找其他的可能性了，然而我們在這裡就會遇到問題了，仿造前面的作法，我們會是移動左界後，繼續將右界往右去枚舉，然而針對新的左界 $l'$，我們所期待他所對應到的右界 $r'$ 不應該會在原本右界的右邊，因為
$$
\begin{cases}
a_{l'} \ge a_l \\
a_{r'} \ge a_r \\
a_l + a_r > t
\end{cases}\Rightarrow a_{l'} + a_{r'} > t
$$
也就是說，我們實際上應該要把右界向左移動才能找到我們的答案，既然如此，我們何不一開始就把右界放在最右邊呢？有了這樣的想法我們就得到了最後的作法：

一開始先將左右界分別放到極左、極右點，接下來將右界向左枚舉，直到找到第一個 $a_l + a_r \ge t$ 的 $(l, r)$，如果 $a_l + a_r = t$ 就代表找到了答案。接下來則是右移左界，然後一樣是將右界繼續向左枚舉，直到找出下一個臨界點，重複以上的作法直到 $l = r$ 為止。

時間複雜度的部份，由於我們知道我們最多就是左右界移動到重疊為止，而左右界每次移動一個、不會回頭，因此會移動 $O(N)$ 次，每次移動的操作都是常數的運算，總複雜度為 $O(N)$。

範例程式碼如下（考量了重複元素的作法）：

int main () {
    int n; // 序列長度
    int t; // 目標大小
    int arr[30001]; // 序列

    cin >> n; // 讀輸入
    cin >> t;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];

    // 左右指標，一開始分別放在極左、極右點
    int l = 1, r = n;
    int sum = arr[l] + arr[r]; // 左右指標指向的數字和

    for (; l < r; ++l) { // 移動左指標。
        // 總和過大，移動右指標來讓總和減小。
        while (sum > t && r > l) {
            sum -= arr[r];
            r--;
            sum += arr[r];
        }

        // 如果總和符合目標，就輸出答案。
        if (sum == t) {
            cout << l << " " << r << '\n';
            return 0;
        }

        // 總和過小，移動左指標來讓總和增加。
        sum -= arr[l];
        sum += arr[l + 1];
    }

    // 題目保證必定有解
    assert(0);

    return 0;
}

接下來我們可以來分析一下前面兩種作法的差異：

我們會發現雙指標在處理這兩題的主要精神都是去微調我們的目標性質：不斷移動右界直到超過臨界值、接著再移動左界讓目標性質回歸臨界值之下，週而復始，用這樣的眼光我們就可以更清楚的了解到兩種不同作法的理由了。

第一道題目中，我們利用到了「區間」擁有的單調性：我們要讓區間和超過臨界值的方式就是讓區間變長、回歸臨界值下則是讓區間變短，因此兩個指標必須要是「順向」的才可以同時滿足這樣的需求，否則區間只會一直的變長或變短，而一直的變長 / 變短只會讓我們的目標性質單純的上升 / 下降而已。

第二道題目則是使用了「元素」本身的單調性：我們左移右界讓總和小於臨界值後，則需要右移左界來讓總和增加，試圖平衡移動右界所帶來的損失，因此我們就得到了「反向」的雙指標。

體會一下兩者間的差異想必可以對他們有更深刻的認識！

「雙指標」其實比較像是一種形式、一種手法，而不是一種很具體的演算法，期望在這個章節中列舉的幾項雙指標最常用的情境能讓讀者們更加的熟悉這樣的技法！