- 【用途】快速查找
- 【實作】
- 設定左右兩個指標，配合目標適時移動其中的一個或兩個。
- 或，每次計算中間指標 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;
}
}
}
}
Post Views (since April 2021) : 4,000