基本雙指針

介紹

#

雙指針（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;
}