基本雙指針

介紹

雙指針（Two pointer）是一種常見的技巧，概念就是用兩個變數指向陣列中不同的位置，然後根據問題的要求，移動這兩個指針。通常可以利用單調性來以更好的時間複雜度解決問題。

合併兩個排序陣列

一個基本的題型是，給定兩個排序過的陣列，要求合併這兩個陣列並且保持排序。

這個問題就可以使用雙指針解決！

也許你已經想到了，我們可以用兩個指針分別指向兩個陣列的開頭，然後比較這兩個位置的元素：

把較小的元素放入答案陣列，然後移動指向這個元素的指針：

接下來繼續比較兩個指針指向的元素：

重複這個過程直到其中一個陣列的元素全部被放入答案陣列：

如此一來，我們就在 $O(n)$ 的時間複雜度內完成了這個問題。

程式碼也非常簡單：

// 雙指針主要的部分
int i = 0, j = 0;
vector<int> ans;
while (i < nums1.size() && j < nums2.size()) {
    if (nums1[i] < nums2[j]) {
        ans.push_back(nums1[i]);
        i++;
    } else {
        ans.push_back(nums2[j]);
        j++;
    }
}

// 把剩下的元素放入答案陣列
while (i < nums1.size()) {
    ans.push_back(nums1[i]);
    i++;
}

while (j < nums2.size()) {
    ans.push_back(nums2[j]);
    j++;
}

當然，從上面的例子可以發現，這個方法只能用在兩個排序過的陣列上。如果陣列沒有排序，那麼這個方法就不適用了。也就是說，大部分的雙指針問題都會依賴於陣列的單調性。

進階題

我們有一個長度為 $n$ 的陣列 $a$ 和一個長度為 $m$ 的陣列 $b$，在兩個陣列皆是排序的情況下，請對於每個 $b_i$ 計算有多少陣列 $a$ 中的元素嚴格小於 $b_i$。

$1 \leq n, m \leq 10^5$，$1 \leq a_i, b_i \leq 10^9$。

解決問題的第一步就是觀察，我們可以在這個問題中看到什麼單調性呢？

如果 $a$ 陣列中存在 $k$ 個比 $b_i$ 小的元素，那麼對於 $b_{i+1}$ 來說，答案一定不會比 $k$ 小。

看看下面的例子，陣列 $b$ 中的 $13$ 有 $3$ 個比它小的元素：

那麼對於 $b$ 中的 $15$ 來說，答案一定不可能比 $3$ 小：

根據這個性質，我們可以使用雙指針解決這個問題：

指針 $i$ 指向陣列 $a$ 目前比較到的位置，指針 $j$ 指向陣列 $b$ 目前比較到的位置，每次指針 $j$ 往右移動時，我們就把指針 $i$ 往右移動直到 $a[i] \geq b[j]$，並把 $i$ 的值當作答案記錄下來。

for (int i = 0, j = 0; j < b.size(); j++) {
    while (i < a.size() && a[i] < b[j]) {
        i++;
    }
    ans[j] = i;
}