【筆記】Two Pointers

  • 【用途】快速查找
  • 【實作】
    • 設定左右兩個指標,配合目標適時移動其中的一個或兩個。
    • 或,每次計算中間指標 mid = (l + r) / 2,配合目標決定下一步改往左半部 (r = mid) 或右半部 (l = mid + 1) 繼續搜尋。
  • 【範例】
    • a[ ] = {6, 2, 1, 3, 9, 8}
    • a[ ] 數列中,是否存在兩個數字,加起來等於 11?

【方法1】Two Pointers:O(N*log(N)) + O(N)

  • 題目只要求判斷是否存在兩個數字,加起來等於 11,而非找出所有可能的組合。
  • 資料先進行排序。
  • 再使用two pointers技巧,依照狀況遞增左邊或遞減右邊的指標。
  • 【複雜度】:排序也需要花時間,所以應該是O(N*log(N)) + O(N)?
void solve3(){
    int l = 0;
    int r = N - 1;
    sort(a, a+N);
    while (l < r){
        if (a[l] + a[r] > target) r--;
        else if (a[l] + a[r] < target) l++;
        else {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

【方法2】暴力枚舉:O(N2)

#include <iostream>
using namespace std;

int N = 6;
int a[] = {6, 2, 1, 3, 9, 8};
int target = 11;

void solve1(){
    for (int i=0; i<N-1; i++){
        for (int j=i+1; j<N; j++){
            if (a[i] + a[j] == target){
                cout << a[i] << " + " << a[j] << " = " << target << endl;
            }
        }
    }
}

int main(){
    solve1();
    return 0;
}

【方法3】也是暴力枚舉:O(N2)

void solve2(){
    for (int i=0; i<N-1; i++){
        int check = target - a[i];
        for (int j=i+1; j<N; j++){
            if (a[j] == check){
                cout << a[i] << " + " << a[j] << " = " << target << endl;
            }
        }
    }
}

分享本文 Share with friends