【C++】競程筆記（雙指標）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

雙指標（Two-Pointer）

雙指標是一種常用於陣列或字串處理的技巧。

顧名思義，雙指標是指同時使用兩個指標（指向資料結構的索引）來遍歷或操作資料。

這種技巧可以減少時間複雜度，能避免掉多重迴圈，常被用在排序陣列或雙向搜尋的情況上。

常見的指標移動方式有：

  • 一個從頭開始、另一個從尾開始（雙向靠攏）
  • 一個快指標、另一個慢指標（追趕法）
  • 同時向同一方向移動但控制條件不同

有一個更快理解什麼是雙指標的例子：

假設有個已經排序好的序列：arr = [1, 3, 4, 5, 7, 10, 11]。

我們希望能找出兩個數的和是 14。

則雙指標的初始狀態：left → 1 3 4 5 7 10 11 ← right

首先走第一遍初始狀態：arr[left] + arr[right] = 12，值太小，需要移動左邊的指標，叫他往右，讓值變大一點。

所以第二遍：arr[left+1] + arr[right] = 14，剛好就找到 14 了。

像這種就是 Two sum 問題。

例題 1

Leetcode 209. Minimum Size Subarray Sum：https://leetcode.com/problems/minimum-size-subarray-sum/description/

最開始會想到的一定都會是暴力解，如這題可用三重迴圈去解決，只是時間複雜度會變成 $O(N^3)$ 。具體解法：

  1. 窮舉出所有 $(l, r)$
  2. 求出所有 $num[l]$ 到 $num[r]$ 的數字總和
  3. 看總和有沒有超過 $target$

雙指標做法：

  1. 使用兩個指標：l 為左界，r 為右界，用來定義一個動態的區間 [l, r]。
  2. r 從頭到尾遍歷陣列，每次將 nums[r] 加入目前的總和 sum。
  3. 每當 sum >= target 時，表示目前這個區間 [l, r] 是一組解（其子陣列總和符合要求）。
  4. 為了找到最短的子陣列和，就要把 l 往右推移，每推一次就更新當前最短長度，直到 sum < target 為止。
  5. 重複步驟 2~4，直到整個陣列走完為止。
  6. 若最後沒有找到任何子陣列和（即最短長度仍為初始最大值），則回傳 0。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size(); // 陣列長度
    int l = 0, sum = 0;
    int minLen = INT_MAX; // 最短的合法子陣列之長度

    for (int r = 0; r < n; r ++){
        sum += nums[r];

        while (sum >= target){
            // 為了找到最小子陣列和
            // 所以把 l 右移
            minLen = min(minLen, r - l + 1);
            sum -= nums[l];
            ++l;
        }
    }
    return (minLen == INT_MAX) ? 0 : minLen;
    // minLen 從來沒變過，都還是 INT_MAX 的話，代表找不到子陣列和，回傳 0
}

時間複雜度： $O(n)$ 。

例題 2

Leetcode 167. Two Sum II - Input Array Is Sorted：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

解題思路：

  1. 初始化兩個指標：left = 0、right = numbers.size() - 1。
  2. 計算 numbers[left] + numbers[right]：
    • 若和 = target：回傳 left + 1 和 right + 1（題目要求 1-indexed）。
    • 若和 < target：表示數字太小，將 left 往右移動。
    • 若和 > target：表示數字太大，將 right 往左移動。
  3. 因為題目保證有唯一解，故不需考慮無解情況。

程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        while (l < r){
            int sum = numbers[l] + numbers[r];
            if (sum == target){
                return {l + 1, r + 1};
            }
            else if (sum < target){
                l++;
            }
            else{
                r--;
            }
        }
        return {};
    }
};

習題

  1. Leetcode 3. Longest Substring Without Repeating Characters：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

解題思路：

  1. 初始化雙指標 l, r。
  2. 用 unordered_set 記錄目前的字元。
  3. 當 r 指到重複的字元，就不斷地從 l 開始移除，直到移除掉所有重複的字元。
  4. 每次更新最大長度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set <char> ch;
        int l = 0, r = 0;
        int maxLen = 0;
        while (r < s.length()){
            // find() 若找不到就指向 ch.end(), 代表這個字母沒出現過
            if (ch.find(s[r]) == ch.end()){
                ch.insert(s[r]);
                maxLen = max(maxLen, r - l + 1);
                r++;
            }
            else{
                ch.erase(s[l]);
                l++;
            }
        }
        return maxLen;
    }
};
  1. Leetcode 977. Squares of a Sorted Array：https://leetcode.com/problems/squares-of-a-sorted-array/description/

解題思路：

原陣列 nums 為非遞減排序，負數平方後可能比正數平方大：

1
2
nums = [-4, -1, 0, 3, 10]
squares = [16, 1, 0, 9, 100]

若直接平方再排序的時間複雜度為 $O(nlogn)$ ，可用雙指標從兩端往中間夾，因為最大的平方數只可能出現在兩端。

  1. 建立左右指標 int l = 0, r = num.size() - 1;。
  2. 建立 result vector，從尾端填入最大的平方值（因為最大平方值在兩端）。
  3. 每次比較 abs(nums[left]) 和 abs(nums[right])，取較大者平方後放到 result[i]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size(); // 陣列長度
        int l = 0, r = n - 1; // 左右指標
        int index = n - 1; // 作為 result vector 的起始點, 也就是最右邊
        // 另外要先塞最大的平方數, 再慢慢遞減下來 ( index-- )
        vector<int> result(n);
        while(l <= r){
            if (abs(nums[l]) > abs(nums[r])){
                result[index--] = nums[l] * nums[l];
                l ++;
            }
            else{
                result[index--] = nums[r] * nums[r];
                r --;
            }
        }
        return result;
    }
};