雙指針?biāo)惴?/h1>
其實(shí)快排和歸并就用到了雙指針?biāo)惴ǎ?/p>
思想與用途：雙指針?biāo)惴梢詫?img class="math-inline" src="https://math.jianshu.com/math?formula=O%7B(n%5E2)%7D" alt="O{(n^2)}" mathimg="1">的復(fù)雜度優(yōu)化成。每一個(gè)指針總共移動(dòng)的次數(shù)是不超過(guò)
n的，兩個(gè)指針總共移動(dòng)的次數(shù)不會(huì)超過(guò)2n 。非常強(qiáng)大好用，將暴力算法優(yōu)化！
- 雙指針?biāo)惴ǖ慕?jīng)典使用
// 分開(kāi)字符串中的word 雙指針做法
#include <iostream>
#include <string.h>
char str[1000];
using namespace std;
int main(){
cin.getline(str,1000); // gets從鍵盤(pán)中讀入到str數(shù)組 gets被禁 使用cin.getline也可以
int n = strlen(str);
for(int i=0;i<n;i++){
int j = i; // 這個(gè)j指針才是具體檢索單詞的指針
while(j < n && str[j]!=' ')j++; // j結(jié)束的時(shí)候在' '處
for(int k=i;k<j;k++) cout << str[k];
cout << endl;
i=j; // 讓i跨到目前的j處
}
return 0;
}
// 當(dāng)然此題使用單指針效率也是O(n)
雙指針?biāo)惴ǖ母拍罘浅V泛
- 最長(zhǎng)不包含重復(fù)數(shù)字連續(xù)子序列
// 1 2 2 3 4 5
// 暴力算法 核心 O(n^2)
for(int j = 0;j<n;j++){ // j是終點(diǎn)指針
for(int i=0;i<j;i++){
check(i,j){
res = Max(res,j-i+1);
}
}
}
// 雙指針?biāo)惴?O(2n)
for(int i=0;i<n;i++){
while(i < j && check(i,j)){
}
}
雙指針?biāo)惴ǘ际菑谋┝λ惴ǜ倪M(jìn)而來(lái)，往往是找出兩個(gè)指針之間的關(guān)系，從而不用全部枚舉數(shù)對(duì)
往往是：暴力算法與雙指針?biāo)惴?第一個(gè)指針都是一樣 掃一遍。雙指針?biāo)惴ǖ牡诙€(gè)指針往往只要掃一遍，而暴力算法來(lái)回的掃若干遍
#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N],cnt[N];
int n;
int main(){
cin >> n;
for(int i=0;i<n;i++){
cin >> a[i];
}
int res = 0;
for(int i = 0,j = 0; i < n ; i++){
cnt[a[i]]++;
while(cnt[a[i]] == 2){ // cnt[a[i]]和cnt[a[j]]修改的是同一個(gè)值，通過(guò)cnt[a[j]]來(lái)改變cnt[a[i]]
cnt[a[j]]--;
j++;
} // 這個(gè)while是核心 結(jié)束的時(shí)候i=j(示例序列是這個(gè))或者 i= j+1
res = max(res,i-j+1);
}
cout << res << endl;
return 0;
}
當(dāng)數(shù)組比較長(zhǎng)的話，可以用hash表來(lái)做。起到 不開(kāi)數(shù)組判重的作用
雙指針?biāo)惴ò咐?br>
給定兩個(gè)升序排序的有序數(shù)組 A 和 B，以及一個(gè)目標(biāo)值 x。
數(shù)組下標(biāo)從 0 開(kāi)始。
請(qǐng)你求出滿足 A[i]+B[j]=x 的數(shù)對(duì) (i,j)。
數(shù)據(jù)保證有唯一解
// 暴力
for(int i = 0; i < m;i++){
for(int j = 0 ; j< n ;j ++){
if (A[i] + B[j] == x){
cout << i << j << endl;
break;
}
}
}
時(shí)間復(fù)雜度，由于A數(shù)組和B數(shù)組都是單調(diào)數(shù)組，因此可以通過(guò)單調(diào)性來(lái)合理的“跳”過(guò)一些比較計(jì)算，只計(jì)算有用的。這就是雙指針對(duì)暴力的優(yōu)化。對(duì)于本題來(lái)說(shuō)具體選用雙指針中的對(duì)撞指針
#include <iostream>
using namespace std;
const int N = 10e5+10;
int A[N],B[N];
int n , m ;
int x;
int main(){
scanf("%d%d%d",&n,&m,&x);
for(int i = 0;i<n;i++){
scanf("%d",&A[i]);
}
for(int j = 0;j<m;j++){
scanf("%d",&B[j]);
}
for(int i = 0,j = m-1;i<n;i++){
while(j >= 0 && A[i] + B[j] >x) j--;
if(A[i] + B[j] == x){
cout << i << " " << j<<endl;
break;
}
}
return 0;
}
本題如果沒(méi)有限制解的個(gè)數(shù)是唯一的話，就不能使用雙指針來(lái)優(yōu)化，只能暴力。
若是兩個(gè)數(shù)組是無(wú)序的話，也能做，使用hash表來(lái)做
